TY - JOUR
T1 - NP-completeness and an approximation algorithm for rectangle escape problem with application to PCB routing
AU - Ma, Qiang
AU - Wong, Martin D.F.
N1 - Funding Information:
Manuscript received September 12, 2011; revised December 21, 2011 and February 28, 2012; accepted March 19, 2012. Date of current version August 22, 2012. This work was supported in part by the National Science Foundation, under Grant CCF-1017516. The preliminary version of this article appeared in the Proceedings of ASPDAC’11 [9]. This paper was recommended by Associate Editor E. Young.
PY - 2012
Y1 - 2012
N2 - In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (PCB) bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-complete, and show that it can be formulated as an integer linear programming (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within several seconds for each of the test cases.
AB - In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (PCB) bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-complete, and show that it can be formulated as an integer linear programming (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within several seconds for each of the test cases.
KW - Approximation algorithm
KW - NP-completeness
KW - linear programming relaxation
KW - printed circuit board (PCB) routing
UR - http://www.scopus.com/inward/record.url?scp=84865345791&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865345791&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2012.2193581
DO - 10.1109/TCAD.2012.2193581
M3 - Article
AN - SCOPUS:84865345791
SN - 0278-0070
VL - 31
SP - 1356
EP - 1365
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 9
M1 - 6269973
ER -