# Approximation algorithm for graph problem

In the process of trying to create an approximation algorithm for the following problem.

Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a finite set of integers. Each vertex $v$ in the graph is to be assigned an element $i$ from the list $L$ at cost $c_{iv}$. Cost $c_e$ is incurred for an edge iff its vertices are in different lists. The objective is to find the minimum cost assignment to vertices.

IP: Minimize $\sum_{e \in E} c_e x_e + \sum_{i \in L \\ v \in V} c_{iv}y_{iv}$ subject to

$\sum_{i \in L} y_{iv} = 1$ for all $v \in V$,

$y_{iv} + y_{ju} \le 1 + x_{(u,v)}$, for all $(u,v) \in E$, $i \neq j \in L$.

$x_e, y_{iv} \in \{0,1\}$ for all $e \in E$, $i \in L$, $v \in V$.

Somehow (through rounding), I am supposed to use the linear relaxation to create a 2-factor approximation for the optimal solution to this integer program. Does anyone have a hint for how to proceed?

• first solve a sample instance and look at the LP relaxation solution. See if you can do some thing with that. My guess is at least one of the variables should take a value greater that 0.5. Fix that and solve it repeatedly. Let me know if this works. If so, then one could go ahead try proving it. – user62089 Mar 27 '13 at 23:05
• By fix it do you mean round it to one? A problem I've encountered is that the optimal solution to the LP could avoid charging any edge (for example, by setting $x_{iv} = \frac{1}{|L|}$ for all $i$, $v$). Then, when I round, inevitably I will create conflicts which will incur edge costs. So somehow I have to bound those ... – Kuhndog Mar 28 '13 at 0:56
• But you're right, it seems that at least the minimum $c_{iv}$ for each vertex $v$ should have $x_{iv}$ value at least 1/2. However, rounding all of those guys to 1 should create edge conflict. @pondy – Kuhndog Mar 28 '13 at 1:00
• Don't round all at one time. Round one in a single iteration. And keep doing it every iteration. That is why the method is called iterative LP rounding – user62089 Mar 28 '13 at 3:58
• What is the reason that you are interested in this problem? – Kaveh Mar 28 '13 at 21:53