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?
The problem you specify is called Uniform Labeling Problem and often arises in the field of computer vision. Kleinberg &amp; Tardos give the LP-based 2-approximation you are looking for.

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