# 2-approximation edge-cover algorithm using primal-dual method

## 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.

1. $y_u + y_v \leq w_e$ for $\forall e=\left(u, v \right) \in E$
2. $y_v \geq 0$ for $\forall v \in V$

## Tentative algorithm

1. $C \leftarrow \emptyset$

2. 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.

• The standard analysis (using only the primal) takes all edges with $x_e \geq 1/2$. Perhaps you can modify this analysis to use the primal-dual approach. Jun 30 '17 at 14:21