In the paper "Improved Algorithm for Degree Bounded Survivable Network Design Problem", by N. Vishnoi and A Louis, have used the iterated rounding approach in a similar as by Jain in designing the approximation algorithm for the steiner network and recently by Mohit Singh et al for the degree bounded case steiner network. The paper improves on the result by Mohit Singh and may however be not optimal.

My query is very specific to the paper i have referred above:

1) In the proof of the main lemma: base case where we have a tight vertex $v$. If we say that degree of vertex $v$ is at least $4$, then it seems to me that the arguments still hold as follows. If there are no heavy edge then everything is good. In case we have a heavy edge e which the paper considers, then since $x_e$ is strictly less than $1$, we again will have at least $4$ other edges(including one light edge) and can get $4$ tokens.

I am interpreting that a tight vertex of degree $4$ has to have edges incident on it whose sum of $x_e$ is $4$.

2) In the induction part, the fact used is that we are maintaining $b(v)$ greater than or equal to $3/2$. Where else are we using this fact? Why cant be $2$ if we are not using anywhere else. (and accordingly changing the algorithm)

I am quite new to approximation algorithm and particularly to this technique. In order to find the underlying hardness, i was playing with the proof and ended up with above 2 things. I am sorry for the fact that the question is heavily dependent on the paper (both the context and notations). Any other suggestion or comment is appreciated.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.