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 -