2008
12.01

SoCG submission #1: Weighted Geometric Set Cover Problems Revisited, with Mira Lee.

  1. The last part, of finding a min-weight set of constraints whose deletion makes an LP feasible, is neat. Do you know of any hardness results for this problem in fixed dimension?

  2. No. I am unaware of any hardness result in constant dimenison directly. The natural conjecture would be that for the unweighted case, for a given k, one can not solve the problem in time better than n*k^{Omega(d)}. Currently, nk^{d} is known. If you are allowed to approximate k, a lower bound of the form (1/eps)^{d} would be very interesting…