Approximation algorithm for graph problem
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.