NP-Completeness and an Approximation Algorithm for Rectangle Escape Problem With Application to PCB Routing

摘要

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.