I'm trying to implement an approximation algorithm for the 0-extension problem

I found the following paper:

Approximation Algorithms for the 0-extension problem by Gruia Calinescu, Howard Karloff and Yuval rabani.

On page 5 they explain the algorithm but I don't understand it (I'm not English and some words are difficult to understand)

so can someone explain the algorithm from an implementation standpoint?

As input data (numbers are for illustration), I have a graph with 64 vertexes and a number of connections (no info about the max degree) every connection has a "distance" defined I want to colour the vertices with 3 colours some vertices already have a colour

How do I do this? I'm pretty advanced software designer so you can use high-level pseudo-code


$\delta(u,v) = d(f(u),f(v))$

What do they mean with $f(\cdot)$? Aren't $d$ and $\delta$ the "distance" functions?

minimize $\sum_{uv \in E} c(u,v) \delta(u,v)$

Where is the $c(\cdot)$ coming from? Cost function?

Rounding procedure:

set $f(t) = t$ for all terminals

Are the terminals the colors or the vertices or vertices with a color assigned?

such that $\delta(u,\sigma_j) \leq \alpha A_u$

What is $A_u$? What is $\sigma_j$?


ok so i need to compose the equasions and solve them with a LP solver

lets take this example: http://i77.photobucket.com/albums/j74/bertyhell/Diagram1.png I want to know what colour to give B and C in this case the best solution is to give C the red colour and B a green colour (B and A are furthest from each other)

2 terminals already have a color and every edge as a "distance" my cost function is:

int c(u,v){
    if(u.color == undef || v.color == undef){
        return undef //unknown cost
    }else if(u.color == v.color){
        return 90 - "distance"
        return 0 //no cost

how do I put this in an equation?

and won't the equation system be undefined if there are to many terminals without a colour?

and if it isn't undefined, wont the first step solve the whole 0-extension problem?

  • 3
    $\begingroup$ It might be helpful if you could highlight which steps were unclear. The algorithm works in two steps: 1. Solve a linear program (described at the top of page 5) and 2. Modify the values produced by the linear program to get a feasible solution (the rounding step). $\endgroup$ Apr 19 '11 at 17:52
  • $\begingroup$ i added more specifics under "edit". $\endgroup$
    – Berty
    Apr 20 '11 at 7:17
  1. Page 1 explains how you can go from the $\delta$-based formulation to the $f$-based formulation and back. But it doesn't matter for the algorithm. The first step is to solve the LP, thus obtaining values for the $\delta(i, j)$ values. From a pseudocode standpoint, you solve this by calling your favorite LP solver.

  2. $c$ is the cost per edge, and is part of the input.

  3. Terminals are the elements of the tree T (also given as part of the input)

  4. $A_u$ is defined in the line above the text 'Rounding procedure' as the minimum distance between u and elements of T.

  5. \sigma_j denotes the jth element of T in some random ordering of the elements (basically scramble the array of indices corresponding to T and take the jth element)

  • $\begingroup$ added extra info under EDIT2, thx for helping me btw, appreciate it $\endgroup$
    – Berty
    Apr 20 '11 at 9:45
  • $\begingroup$ firstly, the function you define is perfectly valid as a cost function, but to run the LP you'd have to precompute all the costs for all pairs of nodes and then hardwire it. Secondly, the whole point of the process is to find the mapping to colors, so having undefined colors initially is the point of the exercise ! In your case, some colors are fixed initially, which corresponds to certain values of the $\delta$ function being fixed. So just hardwire those values when you write your LP constraints. p.s this discussion is getting beyond the scope of this site. $\endgroup$ Apr 20 '11 at 14:16

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.