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

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