3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 30 '17 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.