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

Qiang Ma, Martin D F Wong

Research output: Contribution to journalArticle

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 languageEnglish (US)
Article number6269973
Pages (from-to)1356-1365
Number of pages10
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume31
Issue number9
DOIs
StatePublished - Aug 29 2012

Fingerprint

Approximation algorithms
Printed circuit boards
Linear programming
Computational complexity

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

@article{234bf7fe33e440eabd497bd6b6900d6d,
title = "NP-completeness and an approximation algorithm for rectangle escape problem with application to PCB routing",
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.",
keywords = "Approximation algorithm, NP-completeness, linear programming relaxation, printed circuit board (PCB) routing",
author = "Qiang Ma and Wong, {Martin D F}",
year = "2012",
month = "8",
day = "29",
doi = "10.1109/TCAD.2012.2193581",
language = "English (US)",
volume = "31",
pages = "1356--1365",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

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 -