Partial multicovering and the dd-consecutive ones property

A d-interval is the union of dd disjoint intervals on the real line. In the dd-interval stabbing problem (dd-is) we are given a set of dd-intervals and a set of points, each dd-interval II has a stabbing requirement r(I)r(I) and each point has a weight, and the goal is to find a minimum weight multiset of points that stabs   each dd-interval II at least r(I)r(I) times. In practice there is a trade-off between fulfilling requirements and cost, and therefore it is interesting to study problems in which one is required to fulfill only a subset of the requirements. In this paper we study variants of dd-is in which a feasible solution is a multiset of points that may satisfy only a subset of the stabbing requirements. In partial  dd-is we are given an integer tt, and the sum of requirements satisfied by the computed solution must be at least tt. In prize collecting  dd-is each dd-interval has a penalty that must be paid for every unit of unsatisfied requirement. We also consider a maximization version of prize collecting dd-is in which each dd-interval has a prize that is gained for every time, up to r(I)r(I), it is stabbed. Our study is motivated by several resource allocation and geometric facility location problems. We present a (ρ+d−1ρ)-approximation algorithm for prize collecting dd-is, where ρ=minIr(I)ρ=minIr(I), and an O(d)O(d)-approximation algorithm for partial dd-is. We obtain the latter result by designing a general framework for approximating partial multicovering problems that extends the framework for approximating partial covering problems from Könemann et al. (2011) [14]. We also show that maximum prize collecting dd-is is at least as hard to approximate as maximum independent set, even for d=2d=2, and present a dd-approximation algorithm for maximum prize collecting dd-dimensional rectangle stabbing.

► We design approximation algorithms for multicovering problems.
► We focus on multicovering with the multiple-consecutive ones property.
► We present algorithms for prize-collecting and partial multiple-interval stabbing.
► We design a general framework for approximating partial multicovering problems.