The Subinterval Cover Problem
摘要
In this paper, we introduce the subinterval cover problem. Given a set of interval candidates, each associated with a specific cost factor, we need to select a subinterval from each candidate to cover the entire range. The cost of selecting a subinterval in a candidate interval is determined by multiplying the selected length by the cost factor (the weight). Our goal is to minimize the total cost. This problem has broad applications, such as drone delivery and robot motion planning. Our first finding is that a natural LP formulation of the problem has an unbounded integrality gap, which highlights the challenge of studying this problem. Second, we develop polynomial-time dynamic programming algorithms for two special cases: 1) two distinct cost factors; 2) a constant number of distinct cost factors, and the interval candidates form a laminar set family: each pair of intervals is either disjoint, or one interval contains the other. As a corollary of our dynamic programming algorithm, we design a polynomial-time \(\sqrt{w_{\max }/{w_{\min }}}\) -approximation algorithm for the general cases, where \(w_{\max }\) and \(w_{\min }\) are the maximum and minimum weights of the intervals, respectively.