I'm trying to implement an approximation algorithm for the 0-extension problemI 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 algorithmbut 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 definedI want to colour the vertices with 3 colourssome vertices already have a colourHow do I do this? I'm pretty advanced software designer so you can use high-level pseudo-codeEDIT$\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 terminalsAre 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$?edit2ok so i need to compose the equasions and solve them with a LP solverlets take this example:http://i77.photobucket.com/albums/j74/bertyhell/Diagram1.pngI want to know what colour to give B and Cin 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 colorand every edge as a distancemy 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    }else{        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?
Explain 0-extension algorithm
ds.algorithms;graph algorithms;approximation algorithms;approximation hardness;implementation