Exact Algorithms for Weighted Rectangular Covering Problems

Given n points on a 2-dimensional plane and t types of rectangles of different sizes and weights, the weighted rectangular covering problem (WRCP) aims to cover all the points with rectangles so as to minimize the total weight of the used rectangles. The WRCP is known to be NP-hard and can be solved in \(O(n^6 2^n)\) time. In this paper, we first propose a new algorithm that improves the running time to \(O(\min \{n^5 2^n, tn^3 2^n\})\) . We then consider a special case where each rectangle has zero width or height, in other words, we are given weighted line segments. For the weighted line-segment covering problem (WLSCP), we show that it is still NP-hard and can be solved in \(O(tn 2^n)\) time. We also consider the WLSCP with unit-length line segments and show the problem can be solved in polynomial time.