4
$\begingroup$

Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover?

It is known that set cover problem is $W[2]$ hard when parametrized by the solution size? There might be some advantages when the sets are defined by geometric objects.

$\endgroup$
2
  • $\begingroup$ What is W[2] hardness? $\endgroup$ – Vivek Bagaria Apr 15 '14 at 14:52
  • $\begingroup$ @Bagaria See W hierarchy, and may be before that reading this roughly explanation is easier. $\endgroup$ – Saeed May 19 '14 at 23:13
5
$\begingroup$

The paper D. Marx: Efficient approximation schemes for geometric problems?, in ESA 2005, gives W1-hardness for covering points with unit squares. A draft is here.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.