<ol>
<li><p>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.</p></li>
<li><p>$c$ is the cost per edge, and is part of the input.</p></li>
<li><p>Terminals are the elements of the tree T (also given as part of the input)</p></li>
<li><p>$A_u$ is defined in the line above the text 'Rounding procedure' as the minimum distance between u and elements of T. </p></li>
<li><p>\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)</p></li>
</ol>

CC BY-SA 3.0
2011-04-20T09:45:09.693Z
added extra info under EDIT2, thx for helping me btw, appreciate it
Berty
CC BY-SA 3.0
2011-04-20T14:16:29.913Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-04-20T07:37:34.843Z
2011-04-20T07:37:34.843Z
Suresh Venkat
<p>I'm trying to implement an approximation algorithm for the 0-extension problem</p>

<p>I found the following paper: </p>

<blockquote>
  <p><a href="http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=1FBA2D22588CABDAA8ECF73B41BD3D72?doi=10.1.1.100.8049&amp;rep=rep1&amp;type=pdf" rel="nofollow">Approximation Algorithms for the
  0-extension problem</a> by Gruia
  Calinescu, Howard Karloff and Yuval
  rabani.</p>
</blockquote>

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

<p>so can someone explain the algorithm from an implementation standpoint?</p>

<p>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</p>

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

<p><strong>EDIT</strong></p>

<blockquote>
  <p>$\delta(u,v) = d(f(u),f(v))$</p>
</blockquote>

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

<blockquote>
  <p>minimize $\sum_{uv \in E} c(u,v) \delta(u,v)$</p>
</blockquote>

<p>Where is the $c(\cdot)$ coming from?
Cost function?</p>

<p>Rounding procedure:</p>

<blockquote>
  <p>set $f(t) = t$ for all terminals</p>
</blockquote>

<p>Are the terminals the colors or the vertices or vertices with a color assigned?</p>

<blockquote>
  <p>such that $\delta(u,\sigma_j) \leq \alpha A_u$</p>
</blockquote>

<p>What is $A_u$?
What is $\sigma_j$?</p>

<p><strong>edit2</strong></p>

<p>ok so i need to compose the equasions and solve them with a LP solver</p>

<p>lets take this example:
<a href="http://i77.photobucket.com/albums/j74/bertyhell/Diagram1.png" rel="nofollow">http://i77.photobucket.com/albums/j74/bertyhell/Diagram1.png</a>
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)</p>

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

<pre><code>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
    }
}
</code></pre>

<p>how do I put this in an equation?</p>

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

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

CC BY-SA 3.0
2011-04-19T17:52:38.463Z
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).
Suresh Venkat
CC BY-SA 3.0
2011-04-20T07:17:50.360Z
i added more specifics under "edit".
Berty
<ds.algorithms><graph-algorithms><approximation-algorithms><approximation-hardness><implementation>
Explain 0-extension algorithm
Berty
# Explain 0-extension algorithm

(Asked by: username_0 on 2011-04-19)

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
EDIT

$\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$?
edit2
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"
    }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?

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, approximation-hardness, implementation

> **Comments:**
> **username_1**: 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).  
> **username_0**: i added more specifics under "edit".  

---

## 1 answers

### Answer by username_1 on 2011-04-20. Score: 4

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)

> **Comments:**
> **username_0**: added extra info under EDIT2, thx for helping me btw, appreciate it  
> **username_1**: 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.  

---

