Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Steiner tree approximation via iterative randomized rounding
Byrka J., Grandoni F., Rothvoss T., Sanità L. Journal of the ACM60 (1):1-33,2013.Type:Article
Date Reviewed: Nov 5 2014

The Steiner tree problem is an important combinatorial optimization problem with applications in a wide range of areas, such as very-large-scale integration (VLSI) physical design, the design of virtual private networks, and so on. It is an NP-hard problem and so there has been a good deal of effort to design approximation schemes for it. Of these, the combinatorial algorithm by Robins and Zelikovsky [1] is the best, giving an approximation ratio of 1.55.

The aim of this paper is to give “an LP-based approximation algorithm ... with an improved approximation” ratio, namely, ln(4)+ &egr; < 1.39 for any &egr;. Toward this goal, the paper first presents an LP-relaxation called DCR and a (1+ &egr;) approximate solution. This approximate algorithm is then combined in an iterative randomized rounding technique. Using a lemma called the bridge lemma, it is shown that the expected approximation ratio of this randomized algorithm is ln(4) + &egr; for any &egr;. It is shown how to derandomize this result using the method of limited independence. This leads to a deterministic approximation algorithm with approximation ratio ln(4) + &egr;.

A byproduct of the analysis in this paper is that the integrality gap of the DCR LP is at most 1.55. This answers in the affirmative “a long standing open problem ... whether there is an LP relaxation of [the] Steiner tree [problem] with [an] integrality gap smaller than 2.”

Reviewer:  Krishnaiyan Thulasiraman Review #: CR142896 (1502-0161)
1) Robins, G.; Zelikovsky, A. Tighter bounds for graph Steiner tree approximation. SIAM J. Disc. Math. 19, 1(2005), 122–134.
Bookmark and Share
  Reviewer Selected
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Graph And Tree Search Strategies (I.2.8 ... )
 
 
Trees (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Improving the performance guarantee for approximate graph coloring
Wigderson A. Journal of the ACM 30(4): 729-735, 1983. Type: Article
Feb 1 1985
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Demel J., Demlová M., Koubek V. Theoretical Computer Science 36(2-3): 203-216, 1985. Type: Article
Jan 1 1986
Complexity of the word problem for commutative semigroups of fixed dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy