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 proceedingpeer-review

16 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 languageEnglish
Title of host publicationProceedings of The 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
PublisherIEEE
Pages843-848
Number of pages6
ISBN (Print)9781424475155
DOIs
Publication statusPublished - 28 Jan 2011
Event16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 - Pacifico Yokohama, Yokohama, Japan
Duration: 25 Jan 201128 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

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

Conference

Conference16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Country/TerritoryJapan
CityYokohama
Period25/01/1128/01/11
Internet address

Scopus Subject Areas

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

Fingerprint

Dive into the research topics of 'A provably good approximation algorithm for rectangle escape problem with application to PCB routing'. Together they form a unique fingerprint.

Cite this