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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publication2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Pages843-848
Number of pages6
DOIs
StatePublished - Mar 28 2011
Event2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 - Yokohama, Japan
Duration: Jan 25 2011Jan 28 2011

Publication series

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

Other

Other2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
CountryJapan
CityYokohama
Period1/25/111/28/11

Fingerprint

Approximation algorithms
Polychlorinated biphenyls
Linear programming
Computational complexity

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

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 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 (pp. 843-848). [5722308] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). 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; Young, Evangeline F.Y.

2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011. 2011. p. 843-848 5722308 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ma, Q, Kong, H, Wong, MDF & Young, EFY 2011, A provably good approximation algorithm for rectangle escape problem with application to PCB routing. in 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011., 5722308, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 843-848, 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011, Yokohama, Japan, 1/25/11. https://doi.org/10.1109/ASPDAC.2011.5722308
Ma Q, Kong H, Wong MDF, Young EFY. A provably good approximation algorithm for rectangle escape problem with application to PCB routing. In 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011. 2011. p. 843-848. 5722308. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2011.5722308
Ma, Qiang ; Kong, Hui ; Wong, Martin D F ; Young, Evangeline F.Y. / A provably good approximation algorithm for rectangle escape problem with application to PCB routing. 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011. 2011. pp. 843-848 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@inproceedings{9d15c04f74ba4bd19f70b2ccc66d40bc,
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.}",
year = "2011",
month = "3",
day = "28",
doi = "10.1109/ASPDAC.2011.5722308",
language = "English (US)",
isbn = "9781424475155",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
pages = "843--848",
booktitle = "2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011",

}

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.

PY - 2011/3/28

Y1 - 2011/3/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

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

ER -