| Summary: | 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.<p>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 ℝ<sup><em>d</em></sup> by weighted halfspaces, and provide approximation algorithms and hardness results. We also investigate the <q>dual</q>settings of computing minimum weight simplex that covers a given target point.</p><p>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.</p>
|
|---|