0
$\begingroup$

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows:

Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = \{p_1, \ldots, p_m\} \subseteq 2^X$ be a family of its subsets. Find minimum size sub-family $M$ of $P$ such that $X \subseteq \bigcup \{p \mid p \in M\}$.

An instance of the set cover problem is $\epsilon$-dense if there is $\epsilon > 0$ such that any element of $X$ belongs to at least $\epsilon \, m$ sets from $P$. We show that the dense set cover problem can be approximated with the performance ratio $c \log k$ for any $c > 0$ though it is unlikely to be NP-hard.

In page 3, Lemma 2.1 implies—and Theorem 2.2 proves—that $\epsilon$-DENSE SET COVER is not NP-hard. But, since SET COVER is $\frac{1}{m}$-DENSE SET COVER (any element of $X$ belongs to at least 1 of the $m$ sets), would this mean that SET COVER is not NP-hard?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Their definition is bad, not capturing what they mean. (For every instance of set cover there exists an $\epsilon$ so that it is $\epsilon$-dense....) They mean to define a new problem for every fixed $\epsilon$, which is the $\epsilon$-dense set cover problem, and they mean to define it to be set cover with the promise that all inputs are $\epsilon$-dense for that fixed, constant $\epsilon$. $\endgroup$
    – usul
    Commented Apr 8, 2016 at 11:41

1 Answer 1

Reset to default
2
$\begingroup$

Weighting of elements from set $P$ of SET COVER problem can be obtained by solving a system of linear inequalities for a given $\varepsilon$ that involves $\{0,1\}$-matrix $I=[x_i\in P_j]:$ $Iw\geq\varepsilon\sum\limits_{i=1}^mw_i.$ If it is not feasible then $\varepsilon$-DENSE SET COVER is void. Found weighting can be easily removed by repeating elements of $P$ with respect to the weighting but the resulting problem will be the same. Feasible SET COVER could be reduced to dense one for $\varepsilon=\frac{1}{m}$ but generally aforementioned reduction could lead to void dense problem for constant $\varepsilon.$

In the geometric case when VC-dimension is finite the dense problem with constant $\varepsilon$ could be solved in polynomial time due to result of Haussler and Welzl "epsilon-nets and simplex range queries" claiming existence of feasible solution to $\varepsilon$-dense problem of length $$\frac{8d}{\varepsilon}\log\frac{d}{\varepsilon}.$$ Having upper bound on the problem optimum we could solve te problem by brute-force search. Here $d$ denotes VC-dimension.

Improve this answer
$\endgroup$
5
  • $\begingroup$ So those SET COVER instances for which the system of linear inequalities (for the corresponding $\varepsilon = \frac{1}{m}$) is feasible would be solved optimally in polynomial time, wouldn't they? Otherwise, SET COVER remains NP-hard. $\endgroup$
    – Cromack
    Commented Apr 8, 2016 at 10:49
  • $\begingroup$ I think you misunderstood something in Karpinski book. It is always true that SET COVER is $\frac{1}{m}$-dense otherwise some element of $X$ could not be covered. The system is $Iw\geq\varepsilon\sum\limits_{i=1}^m w_i.$ What I say is the reduction of unweighted SET COVER to dense one given $\varepsilon.$ $\endgroup$
    – KKS
    Commented Apr 8, 2016 at 11:10
  • $\begingroup$ Alright, so SET COVER $\leq_\mathrm{P}$ $\varepsilon$-DENSE SET COVER, according to your reduction. If that is true, and since we know that SET COVER is NP-hard, how is that they say that $\varepsilon$-DENSE SET COVER is unlikely to be NP-hard? That's what I don't understand. $\endgroup$
    – Cromack
    Commented Apr 8, 2016 at 11:20
  • 1
    $\begingroup$ I think that they mean constant $\varepsilon.$ In this case the reduction fails as there are instances of SET COVER that lead to void instance of dense one. $\endgroup$
    – KKS
    Commented Apr 8, 2016 at 11:33
  • $\begingroup$ OK, silly me! haha. Thank you, thank you very much for your help :) $\endgroup$
    – Cromack
    Commented Apr 8, 2016 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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