NDLI: Steiner Tree Approximation via Iterative Randomized Rounding

Content Provider	ACM Digital Library
Author	Byrka, Jarosaw Grandoni, Fabrizio Rothvoss, Thomas Sanit, Laura
Copyright Year	2013
Abstract	The Steiner tree problem is one of the most fundamental $\textbf{NP}-hard$ problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap 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 based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + $\textit{ϵ}$ < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.
Starting Page	1
Ending Page	33
Page Count	33
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2432622.2432628
Journal	Journal of the ACM (JACM)
Volume Number	60
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-02-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithms Linear programming relaxations Network design Randomized algorithms
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Improving Christofides' Algorithm for the s-t Path TSP

Dependent rounding and its applications to approximation algorithms

An improved LP-based approximation for steiner tree

Approximation via cost sharing: Simpler and better approximation algorithms for network design

Convex quadratic and semidefinite programming relaxations in scheduling

An approximation scheme for stochastic linear programming and its application to stochastic integer programs

A unified approach to scheduling on unrelated parallel machines

Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

Steiner Tree Approximation via Iterative Randomized Rounding

Similar Documents

Improving Christofides' Algorithm for the s-t Path TSP

Dependent rounding and its applications to approximation algorithms

An improved LP-based approximation for steiner tree

Approximation via cost sharing: Simpler and better approximation algorithms for network design

Convex quadratic and semidefinite programming relaxations in scheduling

An approximation scheme for stochastic linear programming and its application to stochastic integer programs

A unified approach to scheduling on unrelated parallel machines

Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

Steiner Tree Approximation via Iterative Randomized Rounding