Weighted Geometric Set Cover Problems Revisited

Sariel Har-Peled and Mira Lee.

We study several set cover problems in low dimensional geometric settings. Specifically, we describe a PTAS for the problem of computing a minimum cover of given points by a set of weighted fat objects. Here, we allow the objects to expand by some prespecified delta-fraction of their diameter.

Next, we show that the problem of computing minimum weight cover of points by weighted halfplanes(without expansion) can be solved exactly in the plane. We also study the problem of covering R^d by weighted halfspaces, and provide approximation algorithms and hardness results. We also investigate the "dual" settings of computing minimum weight simplex that covers a given target point.

Finally, we provide a near linear time algorithm for the problem of solving a \LP minimizing the total weight of violated constraints needed to be removed to make it feasible.

Postscript, PDF.

Last modified: Mon Dec 1 14:31:16 CST 2008