### 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 (US) |
---|---|

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

State | Published - Aug 29 2012 |

### Keywords

- Approximation algorithm
- NP-completeness
- linear programming relaxation
- printed circuit board (PCB) routing

### ASJC Scopus subject areas

- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering