Weighted geometric set cover problems revisited

Abstract

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 δ-fraction of their diameter.Next, we show that the problem of computing a minimum weight cover of points by weighted halfplanes (without expansion) can be solved exactly in the plane. We also study the problem of covering ℝd by weighted halfspaces, and provide approximation algorithms and hardness results. We also investigate the dualsettings 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.