TY - GEN
T1 - A provably good approximation algorithm for rectangle escape problem with application to PCB routing
AU - Ma, Qiang
AU - Kong, Hui
AU - Wong, Martin D.F.
AU - Young, Evangeline F.Y.
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - In this paper, we introduce and study the Rectangle Escape Problem (REP), which is motivated by 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 Program (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. This approximation algorithm is also shown to work for a more general version of REP with weights (weighted REP). In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. 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 3 seconds for each of the test cases.
AB - In this paper, we introduce and study the Rectangle Escape Problem (REP), which is motivated by 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 Program (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. This approximation algorithm is also shown to work for a more general version of REP with weights (weighted REP). In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. 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 3 seconds for each of the test cases.
UR - http://www.scopus.com/inward/record.url?scp=79952961886&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952961886&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2011.5722308
DO - 10.1109/ASPDAC.2011.5722308
M3 - Conference contribution
AN - SCOPUS:79952961886
SN - 9781424475155
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 843
EP - 848
BT - 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
T2 - 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Y2 - 25 January 2011 through 28 January 2011
ER -