Name
Abstract | ||
|---|---|---|
Motivated by the bus escape routing problem in printed circuit boards (PCBs), we study the following optimization problem: given a set of rectangles attached to the boundary of a rectangular region, find a subset of nonoverlapping rectangles with maximum total weight. We present an efficient algorithm that solves this problem optimally in ${O(n^{4})}$ time, where ${n}$ is the number of rectangles in the input instance. This improves over the best previous ${O(n^{6})}$ -time algorithm available for the problem. We also present two efficient approximation algorithms for the problem that find near-optimal solutions with guaranteed approximation factors. The first algorithm finds a 2-approximate solution in ${O(n^{2})}$ time, and the second one computes a ${4/3}$ -approximation in ${O(n^{3})}$ time. The experimental results demonstrate the efficiency of both our exact and approximation algorithms. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/TCAD.2016.2585761 | IEEE Trans. on CAD of Integrated Circuits and Systems |
Keywords | Field | DocType |
Approximation algorithms,Routing,Optimized production technology,Heuristic algorithms,Dynamic programming,Printed circuits,Indexes | Maximum disjoint set,Approximation algorithm,Dynamic programming,Electronic engineering,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 3 | 0278-0070 |
Citations | PageRank | References |
2 | 0.39 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| AmirMahdi Ahmadinejad | 1 | 7 | 2.24 |
| Hamid Zarrabi-Zadeh | 2 | 111 | 13.63 |