Abstract
In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (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 programming (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. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. 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 several seconds for each of the test cases.
Original language | English |
---|---|
Article number | 6269973 |
Pages (from-to) | 1356-1365 |
Number of pages | 10 |
Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Volume | 31 |
Issue number | 9 |
DOIs | |
Publication status | Published - 16 Aug 2012 |
User-Defined Keywords
- Routing
- Approximation algorithms
- Approximation methods
- Algorithm design and analysis
- Printed circuits
- Linear programming
- Approximation algorithm
- linear programming relaxation
- NP-completeness
- printed circuit board (PCB) routing