2
$\begingroup$

I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem.

The linear programming problem would became:

Let $0\leq t\leq 1$ be the threshold (as a parameter)

\begin{align} &\min \sum_{v \in V} x_v \\ \text{s.t.}\;\; & x_u + x_v \geq 2t &&\text{for every } (u,v) \in E \\ & 0 \leq x_v \leq 1 &&\text{for every } v \in V \end{align}

And the returned set is $S=\{v:x_v\geq t\}$

When $t=1/2$ this problem would have an approximation with a factor of 2. Initially I thought the factor would always be $1/t$, but if $t=1$ then all nodes would be inserted into the vertex cover.

$\endgroup$
1
  • $\begingroup$ Under the unique games conjecture, approximating vertex cover with a better factor than $2$ is NP-complete, so I doubt you can get a better result by choosing a better $t$ $\endgroup$
    – caduk
    Oct 20, 2023 at 8:04

1 Answer 1

2
$\begingroup$

Bazzi, Fiorini, Pokutta, and Svensson showed in their paper No small linear program approximates Vertex Cover within a factor $2-\varepsilon$ that every polynomial size LP relaxation of Vertex Cover has integrality gap $2-\varepsilon$, meaning (essentially) that any one-step rounding scheme cannot improve the approximation ratio beyond $2$.

This doesn't preclude the theoretical possibility that an iterative rounding scheme (see the monograph Iterative methods in combinatorial optimization by Lau, Ravi and Singh) can be used to obtain an improved approximation, but this is considered unlikely since it is UGC-hard to approximate Vertex Cover within $2 - \varepsilon$, as shown by Khot and Regev in their paper Vertex Cover might be hard to approximate to within $2-\varepsilon$.

$\endgroup$

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.