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

### Fingerprint

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

### Cite this

**NP-completeness and an approximation algorithm for rectangle escape problem with application to PCB routing.** / Ma, Qiang; Wong, Martin D F.

Research output: Contribution to journal › Article

*IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, vol. 31, no. 9, 6269973, pp. 1356-1365. https://doi.org/10.1109/TCAD.2012.2193581

}

TY - JOUR

T1 - NP-completeness and an approximation algorithm for rectangle escape problem with application to PCB routing

AU - Ma, Qiang

AU - Wong, Martin D F

PY - 2012/8/29

Y1 - 2012/8/29

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

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

KW - Approximation algorithm

KW - NP-completeness

KW - linear programming relaxation

KW - printed circuit board (PCB) routing

UR - http://www.scopus.com/inward/record.url?scp=84865345791&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865345791&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2012.2193581

DO - 10.1109/TCAD.2012.2193581

M3 - Article

AN - SCOPUS:84865345791

VL - 31

SP - 1356

EP - 1365

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 9

M1 - 6269973

ER -