Local search strikes again: PTAS for variants of geometric covering and packing

摘要

Geometric Covering and Packing problems have been extensively studied in the last fewdecades and have applications in diverse areas. Several variants and generalizations of these problems have been studied recently. In this paper, we look at the following covering variants where we require that each point is "uniquely" covered, i.e., it is covered by exactly one object: Unique Coverage problem, where we want to maximize the number of uniquely covered points and Exact Cover problem, where we want to uniquely cover every point and minimize the number of objects used for covering. We also look at the following generalizations: Multi Cover problem, a generalization of Set Cover, the objective is to select the minimum subset of objects with the constraint that each input point p is covered by at least d(p) objects in the solution, where dp is the demand of point p. And Shallow Packing problem, a generalization of Packing problem, where we want to select the maximum subset of objects with the constraint that any point in the plane is contained in at most k objects in the solution. The above problems are NP-hard even for unit squares in the plane. Thus, the focus has been on obtaining good approximation algorithms. Local search has been quite successful in the recent past in obtaining good approximation algorithms for a wide variety of problems. We consider the Unique Coverage and Multi Cover problems on non-piercing objects, which is a broad class that includes squares, disks, pseudo-disks, etc. and show that the local search algorithm yields a PTAS approximation under the assumption that the depth of every input point is at most some fixed constant. For Unique Coverage we further assume that every object has at most a constant degree. For the Shallow Packing problem, we show that the local search algorithm yields a PTAS approximation for objects with sub-quadratic union complexity, which is a very broad class of objects that even includes non-piercing objects. For the Exact Cover problem, we show that finding a feasible solution is NP-hard even for unit squares in the plane, thus negating the existence of polynomial time approximation algorithms.