Treffer: Partial multicovering and the -consecutive ones property

Abstract: A is the union of disjoint intervals on the real line. In the -interval stabbing problem (-is) we are given a set of -intervals and a set of points, each -interval has a stabbing requirement and each point has a weight, and the goal is to find a minimum weight multiset of points that stabs each -interval at least 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 -is in which a feasible solution is a multiset of points that may satisfy only a subset of the stabbing requirements. In partial -is we are given an integer , and the sum of requirements satisfied by the computed solution must be at least . In prize collecting -is each -interval has a penalty that must be paid for every unit of unsatisfied requirement. We also consider a maximization version of prize collecting -is in which each -interval has a prize that is gained for every time, up to , it is stabbed. Our study is motivated by several resource allocation and geometric facility location problems. We present a -approximation algorithm for prize collecting -is, where , and an -approximation algorithm for partial -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) . We also show that maximum prize collecting -is is at least as hard to approximate as maximum independent set, even for , and present a -approximation algorithm for maximum prize collecting -dimensional rectangle stabbing. [Copyright &y& Elsevier]