Steiner Tree Approximation via Iterative Randomized Rounding
作者： Jarosław Byrka , Fabrizio Grandoni , Thomas Rothvoß , Laura Sanità , None
关键词:
摘要: … smaller than 2 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is …
uni.wroc.pl
acm.org
core.ac.uk 参考文章(52)
Fabrizio Grandoni, Thomas Rothvoß, Approximation algorithms for single and multi-commodity connected facility location integer programming and combinatorial optimization. pp. 248- 260 ,(2011) , 10.1007/978-3-642-20807-2_20
Pawel Winter, Dana Scott Richards, Frank Hwang, The Steiner Tree Problem ,(1992)
MAREK KARPINSKI, ALEXANDER ZELIKOVSKY, New Approximation Algorithms for the Steiner Tree Problems Journal of Combinatorial Optimization. ,vol. 1, pp. 47- 65 ,(1997) , 10.1023/A:1009758919736
Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani, New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem Integer Programming and Combinatorial Optimization. pp. 344- 358 ,(2008) , 10.1007/978-3-540-68891-4_24
Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach Cambridge University Press. ,(2009) , 10.1017/CBO9780511804090
Fabrizio Grandoni, Giuseppe F. Italiano, Improved Approximation for Single-Sink Buy-at-Bulk Algorithms and Computation. pp. 111- 120 ,(2006) , 10.1007/11940128_13
Daniel Mölle, Stefan Richter, Peter Rossmanith, A faster algorithm for the steiner tree problem symposium on theoretical aspects of computer science. pp. 561- 570 ,(2006) , 10.1007/11672142_46
Eli Upfal, Michael Mitzenmacher, Probability and Computing: Randomized Algorithms and Probabilistic Analysis ,(2005)
Kunal Talwar, The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap integer programming and combinatorial optimization. pp. 475- 486 ,(2002) , 10.1007/3-540-47867-1_33
Deeparnab Chakrabarty, David Pritchard, Jochen Könemann, Hypergraphic LP relaxations for steiner trees integer programming and combinatorial optimization. pp. 383- 396 ,(2010) , 10.1007/978-3-642-13036-6_29