2
$\begingroup$

The wikipedia article of the set cover problem stated the following point regarding the inapproximability of the greedy method "When $n$ refers to the size of the universe.... it cannot be approximated to $\left( {1 - o\left( 1 \right)} \right)\ln \left( n \right)$ unless P = NP". Now suppose that I have the toy example (integer programming formulation) of a simple set cover problem

$\begin{array}{*{20}{c}} {\mathop {\min }\limits_{{x_i} \in \left\{ {0,1} \right\}} }&{{x_1} + {x_2} + {x_3} + {x_4}}\\ {}&{{x_1} + {x_2} \ge 1}\\ {}&{{x_2} + {x_3} \ge 1}\\ {}&{{x_1} + {x_3} + {x_4} \ge 1}\\ {}&{{x_1} + {x_4} \ge 1}\\ {}&{{x_2} + {x_3} + {x_4} \ge 1} \end{array}$

Does this mean that $n$ from the wikipedia article refers to the number of decision variables (4 in this case) or the number of constraints (5 in this case). Particularly, I want to know if $\ln \left( n \right)$ refers to the number of decision variables or the number of constraints when talking about the approximation ratio?

Would you kindly help me with this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

$n$ is the number of elements. Elements are what needs to be covered; therefore, the constraints.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you add a little bit more context ? $\endgroup$
    – Tuong Nguyen Minh
    Commented Jul 23 at 7:17
  • $\begingroup$ @TuongNguyenMinh what do you mean? $\endgroup$
    – fontanf
    Commented Jul 23 at 12:53
  • $\begingroup$ So in my question $n=2$ right ? $\endgroup$
    – Tuong Nguyen Minh
    Commented Jul 23 at 15:13
  • 1
    $\begingroup$ @TuongNguyenMinh $n = 5$ in your example $\endgroup$
    – fontanf
    Commented Jul 24 at 10:41

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.