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?

  • $\begingroup$ 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. $\endgroup$ – user62089 Mar 27 '13 at 23:05
  • $\begingroup$ 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 ... $\endgroup$ – Kuhndog Mar 28 '13 at 0:56
  • $\begingroup$ 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 $\endgroup$ – Kuhndog Mar 28 '13 at 1:00
  • $\begingroup$ 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 $\endgroup$ – user62089 Mar 28 '13 at 3:58
  • 1
    $\begingroup$ What is the reason that you are interested in this problem? $\endgroup$ – Kaveh Mar 28 '13 at 21:53

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 you are looking for.

This problem also appears in the Williamson & Shmoys book as exercise 5.10.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.