Finding Maximum Disjoint Set of Boundary Rectangles with Application to PCB Routing
AmirMahdi Ahmadinejad, Hamid Zarrabi-Zadeh · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2016
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(n4) time, where n is the number of rectangles in the input instance. This improves over the best previous O(n6)-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(n2) time, and the second one computes a 4/3-approximation in O(n3) time. The experimental results demonstrate the efficiency of both our exact and approximation algorithms.