1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\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, 2013 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, 2013 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, 2013 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, 2013 at 3:58
  • 1
    $\begingroup$ What is the reason that you are interested in this problem? $\endgroup$
    – Kaveh
    Mar 28, 2013 at 21:53

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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