<p>The simplest node-weighted network design problem is the node-weighted Steiner tree problem. Klein and Ravi considered this problem and obtained an $O(\log k)$-approximation (here $k$ is the number of terminals). They also showed that the Set Cover problem reduces to it in an approximation preserving fashion and hence we should not expect any better approximation. It is not hard to show that iterated rounding is not helpful for the  Set Cover problem. Consider the following example. We have $n$ elements $\{e_1,\ldots,e_n\}$ and $n$ sets $S_1,\ldots,S_n$ where $S_i$ contains all elements except $e_i$. If you look at the natural LP with a variable $x_i$ for set $S_i$ then a basic feasible optimal solution is to set $x_i = 1/(n-1)$ for each $i$. From this one can see that iterated rounding in the plain vanilla fashion won't give a good bound. Note that the integrality gap of the LP is $O(\log n)$. This example for Set Cover can be extended to the node-weighted Steiner tree problem. </p>

CC BY-SA 3.0
2012-01-25T04:17:04.010Z
2012-01-25T04:17:04.010Z
Chandra Chekuri
<p>I am referring to the "Iterative Rounding" technique used by Kamal Jain for Steiner Network problem to obtain $2$ approximation factor algorithm. Is there any example where this technique is used for vertex weighted graphs? I have only seen examples for weighted edges or edge connectivity problems that use this paradigm. The nearest i have seen is degree bounded networks that use this paradigm. Also, i would like to get some intuition that when is this method probably applicable (or what could be the underlying difficulty that it is not yet applied to vertex weighted scenarios).</p>

CC BY-SA 3.0
2012-01-24T14:48:20.433Z
What's a difference between vertex weighted or edge weighted? Do you think you can find a general approach to apply iterative rounding to vertex weighted related problems? I don't think so. but you can see more iterative rounding in TSP and ATSP (but again they are edge weighted ones).
Saeed
CC BY-SA 3.0
2012-01-24T17:15:45.457Z
vertex weighted is used here for problems that consider weight function on vertices. Similarly, edge weighted is for edges. Sorry for being unclear. I am still trying to learn/access the limitations of this approach. It's difficult to see them in vertex weighted scenarios. The question is therefore asked so that if anyone of you can give some intuition that explains reason behind this limitation.
singhsumit
CC BY-SA 3.0
2012-01-24T18:52:29.717Z
problems which involve vertex weighted functions are more general. replace each edge by one vertex and then transform problem from edge weighted to vertex weighted.
singhsumit
CC BY-SA 3.0
2012-01-24T19:55:59.910Z
I can't get how you do such a transformation, and sure any transformation is not general, but I mean IMO you can't get a general approach for running iterative rounding approach, in fact you should think yourself for your own problem (Also you can ask it here) and there is no general rule. (These are all my opinion, just graduate student, I'm not expert).
Saeed
<graph-algorithms><approximation-algorithms><linear-programming><iterated-rounding>
Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?
singhsumit
# Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?

(Asked by: username_0 on 2012-01-24)

I am referring to the "Iterative Rounding" technique used by Kamal Jain for Steiner Network problem to obtain $2$ approximation factor algorithm. Is there any example where this technique is used for vertex weighted graphs? I have only seen examples for weighted edges or edge connectivity problems that use this paradigm. The nearest i have seen is degree bounded networks that use this paradigm. Also, i would like to get some intuition that when is this method probably applicable (or what could be the underlying difficulty that it is not yet applied to vertex weighted scenarios).

**Tags:** graph-algorithms, approximation-algorithms, linear-programming, iterated-rounding
> **Comments:**
> **username_1**: What's a difference between vertex weighted or edge weighted? Do you think you can find a general approach to apply iterative rounding to vertex weighted related problems? I don't think so. but you can see more iterative rounding in TSP and ATSP (but again they are edge weighted ones).  
> **username_0**: vertex weighted is used here for problems that consider weight function on vertices. Similarly, edge weighted is for edges. Sorry for being unclear. I am still trying to learn/access the limitations of this approach. It's difficult to see them in vertex weighted scenarios. The question is therefore asked so that if anyone of you can give some intuition that explains reason behind this limitation.  
> **username_0**: problems which involve vertex weighted functions are more general. replace each edge by one vertex and then transform problem from edge weighted to vertex weighted.  
> **username_1**: I can't get how you do such a transformation, and sure any transformation is not general, but I mean IMO you can't get a general approach for running iterative rounding approach, in fact you should think yourself for your own problem (Also you can ask it here) and there is no general rule. (These are all my opinion, just graduate student, I'm not expert).  

---

## 1 answers

### Answer by username_2 on 2012-01-25. Score: 6 | Accepted answer

The simplest node-weighted network design problem is the node-weighted Steiner tree problem. Klein and Ravi considered this problem and obtained an $O(\log k)$-approximation (here $k$ is the number of terminals). They also showed that the Set Cover problem reduces to it in an approximation preserving fashion and hence we should not expect any better approximation. It is not hard to show that iterated rounding is not helpful for the Set Cover problem. Consider the following example. We have $n$ elements $\{e\_1,\ldots,e\_n\}$ and $n$ sets $S\_1,\ldots,S\_n$ where $S\_i$ contains all elements except $e\_i$. If you look at the natural LP with a variable $x\_i$ for set $S\_i$ then a basic feasible optimal solution is to set $x\_i = 1/(n-1)$ for each $i$. From this one can see that iterated rounding in the plain vanilla fashion won't give a good bound. Note that the integrality gap of the LP is $O(\log n)$. This example for Set Cover can be extended to the node-weighted Steiner tree problem.


---

