<p>The problem you specify is called <em>Uniform Labeling Problem</em> and often arises in the field of computer vision. Kleinberg &amp; Tardos give the LP-based <a href="http://www.cs.cornell.edu/home/kleinber/focs99-mrf.pdf" rel="nofollow">2-approximation</a> you are looking for.</p>

<p>This problem also appears in the Williamson &amp; Shmoys <a href="http://www.designofapproxalgs.com" rel="nofollow">book</a> as exercise 5.10.</p>

CC BY-SA 3.0
2013-03-29T07:28:29.537Z
2013-03-29T07:28:29.537Z
user7073
<p>In the process of trying to create an approximation algorithm for the following problem.</p>

<p>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.</p>

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

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

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

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

<p>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?</p>

CC BY-SA 3.0
2013-03-27T23:05:11.570Z
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
CC BY-SA 3.0
2013-03-28T00:56:38.210Z
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
CC BY-SA 3.0
2013-03-28T01:00:27.570Z
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
CC BY-SA 3.0
2013-03-28T03:58:55.250Z
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
CC BY-SA 3.0
2013-03-28T21:53:44.417Z
What is the reason that you are interested in this problem?
Kaveh
CC BY-SA 3.0
2013-03-28T22:05:41.977Z
It is an exercise to help me understand the role of linear programming in the design of approximation algorithms.
Kuhndog
<ds.algorithms><graph-algorithms><approximation-algorithms><linear-programming>
Approximation algorithm for graph problem
Kuhndog
# Approximation algorithm for graph problem

(Asked by: username_0 on 2013-03-27)

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?

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, linear-programming
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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 ...  
> **username_0**: 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  
> **username_1**: 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  
> **username_2**: What is the reason that you are interested in this problem?  
> **username_0**: It is an exercise to help me understand the role of linear programming in the design of approximation algorithms.  

---

## 1 answers

### Answer by username_3 on 2013-03-29. Score: 3 | Accepted answer

The problem you specify is called *Uniform Labeling Problem* and often arises in the field of computer vision. Kleinberg & Tardos give the LP-based [2-approximation](http://www.cs.cornell.edu/home/kleinber/focs99-mrf.pdf) you are looking for.

This problem also appears in the Williamson & Shmoys [book](http://www.designofapproxalgs.com) as exercise 5.10.


---

