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).
Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?
graph algorithms;approximation algorithms;linear programming;iterated rounding
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. 