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