2
$\begingroup$

I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not understand why the approximate solution $$\sum_u w_u x^*_u \leq OPT$$

where $w_u$ is the weight to each vertex and $x^*_u$ is the approximate solution to the vertex cover problem and $0 \leq x_u^* \leq 1$

Can someone provide an explanation on how it is possible for the equation above ?

$\endgroup$

1 Answer 1

2
$\begingroup$

Let's start with an integer program for vertex cover:

\begin{align} &\min \sum_{v \in V} x_v \\ \text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\ & x_v \in \{0,1\} &&\text{for every } v \in V \end{align} Here $V$ is the set of vertices and $E$ is the set of edges.

The optimal solution for this integer program is the minimum vertex cover in the graph. We denote its value by OPT.

Unfortunately integer programming is NP-hard to solve exactly, so we consider a linear programming relaxation, replacing the constraint $x_v \in \{0,1\}$ by the constraint $x_v \in [0,1]$:

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

Every feasible solution of the original integer program is also a feasible solution of the linear programming relaxation. In other words, the linear program is minimizing over a set of solutions which contains the set of solutions to the integer program. Therefore the optimal value of the linear program is bounded from above by OPT.

More abstractly, if $A \subseteq B$ then $$ \min_{x \in B} \phi(x) \leq \min_{x \in A} \phi(x). $$ In our case, $A$ is the set of solutions to the integer program, $B$ is the set of solutions of the linear program, and $\phi$ is the objective function $\sum_{v \in V} x_v$.

$\endgroup$
2
  • $\begingroup$ shouldn't the optimal solution to the LP be worse than the optimal vertex cover because the vertex set it generates is an approximation to the problem ? $\endgroup$
    – calveeen
    Commented Nov 27, 2020 at 13:43
  • $\begingroup$ The LP is optimizing over a larger set of potential solutions, so it can only find a better solution than the IP. $\endgroup$ Commented Nov 27, 2020 at 13:51

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.