Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem |
| |
Authors: | Xiuzhen Cheng Bhaskar DasGupta and Bing Lu |
| |
Institution: | (1) Computer Science Department, University of Minnesota, Minneapolis, MN 55455, USA;(2) Rutgers University campus at Camden, USA |
| |
Abstract: | The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem. |
| |
Keywords: | PTAS Rectilinear Steiner Arborescence Symmetric Rectilinear Steiner Arborescence Guillotine Approximation Algorithm |
本文献已被 SpringerLink 等数据库收录! |