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– user620892013年03月27日 23:05:11 +00:00Commented 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– Kuhndog2013年03月28日 00:56:38 +00:00Commented 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– Kuhndog2013年03月28日 01:00:27 +00:00Commented 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– user620892013年03月28日 03:58:55 +00:00Commented Mar 28, 2013 at 3:58
-
1$\begingroup$ What is the reason that you are interested in this problem? $\endgroup$Kaveh– Kaveh2013年03月28日 21:53:44 +00:00Commented Mar 28, 2013 at 21:53
1 Answer 1
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.
Explore related questions
See similar questions with these tags.