6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Saeed Jan 24 '12 at 14:48
  • $\begingroup$ 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. $\endgroup$ – singhsumit Jan 24 '12 at 17:15
  • $\begingroup$ 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. $\endgroup$ – singhsumit Jan 24 '12 at 18:52
  • $\begingroup$ 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). $\endgroup$ – Saeed Jan 24 '12 at 19:55
5
$\begingroup$

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.

$\endgroup$

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.