The problem
Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle.
So far I managed to represent the problem with a linear program:
Linear Program
Primal
$\min \underset{e\in E}{\sum} w_e x_e$
s.t.
- $\underset{e|v\in e}{\sum}x_e\geq 1$ for $\forall v\in V$
- $x_e \geq 0$ for $\forall e \in E$
Dual
$\max \underset{v\in V}{\sum} y_v$
s.t.
- $y_u + y_v \leq w_e$ for $\forall e=\left(u, v \right) \in E$
- $y_v \geq 0$ for $\forall v \in V$
Tentative algorithm
$C \leftarrow \emptyset$
while $C$ is not a cover
2.1. Pick a node $v$ which is not covered
2.2. Increase $y_v$ until a contrains $y_u + y_v \leq w_e$ becomes tight for some $e$
2.3. $C \leftarrow C \bigcup \left\{ e \right\}$
Initial analysis
Since for every $e \in C$ the corresponding constraint is tight, then $\underset{e\in C}{\sum}w_e = \underset{e=\left(u, v \right) \in C}{\sum}y_u+y_v$. Also, since the dual solution is feasible, it must be that $\underset{v\in V}{\sum}y_v \leq \left| OPT \right|$.
So far I've managed to bound it by $d$ which is the highest degree in $G$, since $\underset{e=\left(u, v \right) \in C}{\sum}y_u+y_v \leq \underset{v|e=\left(u,v \right)\in C}{\sum}d \cdot y_v$. This is very similar to the classic version of set-cover using the primal-dual method.
I wonder if and how the analysis can be improved so it provides a 2-approximation ratio.
