A provably good approximation algorithm for rectangle escape problem with application to PCB routing

Qiang Ma; Hui Kong; Martin D. F. Wong; Evangeline F. Y. Young

doi:10.1109/ASPDAC.2011.5722308

A provably good approximation algorithm for rectangle escape problem with application to PCB routing

Qiang Ma, Hui Kong, Martin D. F. Wong, Evangeline F. Y. Young

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

19 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Publisher	IEEE
Pages	843-848
Number of pages	6
ISBN (Print)	9781424475155
DOIs	https://doi.org/10.1109/ASPDAC.2011.5722308
Publication status	Published - 28 Jan 2011
Event	16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 - Pacifico Yokohama, Yokohama, Japan Duration: 25 Jan 2011 → 28 Jan 2011 https://www.aspdac.com/aspdac2011/ (Conference website) https://www.aspdac.com/aspdac2011/archive/program/ (Conference programme) https://ieeexplore.ieee.org/xpl/conhome/5716646/proceeding (Conference proceedings)

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
ISSN (Print)	2153-6961
ISSN (Electronic)	2153-697X

Conference

Conference	16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Country/Territory	Japan
City	Yokohama
Period	25/01/11 → 28/01/11
Internet address	https://www.aspdac.com/aspdac2011/ (Conference website) https://www.aspdac.com/aspdac2011/archive/program/ (Conference programme) https://ieeexplore.ieee.org/xpl/conhome/5716646/proceeding (Conference proceedings)

Access to Document

10.1109/ASPDAC.2011.5722308

Cite this

Ma, Q., Kong, H., Wong, M. D. F., & Young, E. F. Y. (2011). A provably good approximation algorithm for rectangle escape problem with application to PCB routing. In Proceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 (pp. 843-848). (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). IEEE. https://doi.org/10.1109/ASPDAC.2011.5722308

@inproceedings{2e5174447f764a68bce3bd65435ad5ab,

title = "A provably good approximation algorithm for rectangle escape problem with application to PCB routing",

abstract = "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.",

author = "Qiang Ma and Hui Kong and Wong, {Martin D. F.} and Young, {Evangeline F. Y.}",

note = "This work was partially supported by the National Science Foundation under grant CCF-1017516.; 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 ; Conference date: 25-01-2011 Through 28-01-2011",

year = "2011",

month = jan,

day = "28",

doi = "10.1109/ASPDAC.2011.5722308",

language = "English",

isbn = "9781424475155",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

publisher = "IEEE",

pages = "843--848",

booktitle = "Proceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011",

address = "United States",

url = "https://www.aspdac.com/aspdac2011/, https://www.aspdac.com/aspdac2011/archive/program/, https://ieeexplore.ieee.org/xpl/conhome/5716646/proceeding",

}

Ma, Q, Kong, H, Wong, MDF & Young, EFY 2011, A provably good approximation algorithm for rectangle escape problem with application to PCB routing. in Proceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, IEEE, pp. 843-848, 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011, Yokohama, Japan, 25/01/11. https://doi.org/10.1109/ASPDAC.2011.5722308

A provably good approximation algorithm for rectangle escape problem with application to PCB routing. / Ma, Qiang; Kong, Hui; Wong, Martin D. F. et al.
Proceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011. IEEE, 2011. p. 843-848 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

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 - This work was partially supported by the National Science Foundation under grant CCF-1017516.

PY - 2011/1/28

Y1 - 2011/1/28

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

U2 - 10.1109/ASPDAC.2011.5722308

DO - 10.1109/ASPDAC.2011.5722308

M3 - Conference proceeding

AN - SCOPUS:79952961886

SN - 9781424475155

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 843

EP - 848

BT - Proceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011

PB - IEEE

T2 - 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011

Y2 - 25 January 2011 through 28 January 2011

ER -

Ma Q, Kong H, Wong MDF, Young EFY. A provably good approximation algorithm for rectangle escape problem with application to PCB routing. In Proceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011. IEEE. 2011. p. 843-848. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). doi: 10.1109/ASPDAC.2011.5722308

A provably good approximation algorithm for rectangle escape problem with application to PCB routing

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this