A primal-dual approximation algorithm for generalized Steiner network problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A primal-dual approximation algorithm for generalized Steiner network problems

Full text

Pdf (985 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 708 - 717

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

David P. Williamson
Michel X. Goemans
Milena Mihail
Vijay V. Vazirani

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 74, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167268 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ajit Agrawal , Philip Klein , R. Ravi, When trees collide: an approximation algorithm for the generalized Steiner problem on networks, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.134-144, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103437]
	2	Piotr Berman , Viswanathan Ramaiyer, Improved approximations for the Steiner tree problem, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.325-334, September 1992, Orlando, Florida, United States
	3	G.N. Frederickson and J. Ja'Ja', "Approximation algorithms for several graph augmentation problems#, SIAM J. Comput. 10, 270-283 (1981).
	4	H.N. Gabow, M.X. Goemans, and D.P. Williamson, "An Efficient Approximation Algorithm for the Survivable Network Design Problem,# to appear in Proc. Third Conlerence on Integer Programming and Combinatorial Optimization.
	5	Michel X. Goemans , Dimitris J. Bertsimas, Survivable networks, linear programming relaxations and the parsimonious property, Mathematical Programming: Series A and B, v.60 n.2, p.145-166, June 24, 1993
	6	Michel X. Goemans , David P. Williamson, A general approximation technique for constrained forest problems, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.307-316, September 1992, Orlando, Florida, United States
	7	M. Gr6tschel, C.L. Monm# and M. Stoer, "Design of survivable networks", to appear in the Handbook in Operations Research and Management Science, Eds: Michael Ball, Thomas Magnanti, Clyde Monma, and George Nemhauser (1992).
	8	Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, University of Maryland at College Park, College Park, MD, 1992
	9	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	10	R. Ravi , Philip Klein, When Cycles Collapse: A General Approximation Technique for Constrained Two-Connectivity Problems, Brown University, Providence, RI, 1992
	11	H. S#ran, V. Vazirani, and N. Young, "A primaldual approach to approximation algorithms for network Steiner problems", Proc. of lndo-US workshop on Cooperative Research in Computer Science, Bangalore, India, 166-168 (1992).
	12	A.Z. Zelikovsky, "The 11/6 approximation algorithm for the Steiner problem on networks", to appear in Information and Computation.

CITED BY 13

	Milena Mihail , David Shallcross , Nate Dean , Marco Mostrel, A commercial application of survivable network design: ITP/INPLANS CCS network topology analyzer, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.279-287, January 28-30, 1996, Atlanta, Georgia, United States
	Dimitris Bertsimas , Chung-Piaw Teo, From valid inequalities to heuristics: a unified view of primal-dual approximation algorithms in covering problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.102-111, January 22-24, 1995, San Francisco, California, United States
	M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
	Piotr Krysta, Approximating minimum size {1,2}-connected networks, Discrete Applied Mathematics, v.125 n.2-3, p.267-288, February 2003
	Manica Aggarwal , Naveen Garg, A scaling technique for better network design, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.233-240, January 23-25, 1994, Arlington, Virginia, United States
	Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
	R. Ravi , David P. Williamson, An approximation algorithm for minimum-cost vertex-connectivity problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.332-341, January 22-24, 1995, San Francisco, California, United States
	Anupam Gupta , Jon Kleinberg , Amit Kumar , Rajeev Rastogi , Bulent Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.389-398, July 2001, Hersonissos, Greece
	R. C. Chakinala , A. Kumarasubramanian , K. A. Laing , R. Manokaran , C. Pandu Rangan , R. Rajaraman, Playing push vs pull: models and algorithms for disseminating dynamic data in networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.1-10, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Samir Khuller , Balaji Raghavachari , Neal E. Young, Approximating the minimum equivalent digraph, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.177-186, January 23-25, 1994, Arlington, Virginia, United States
	Thomas Moscibroda , Roger Wattenhofer, Facility location: distributed approximation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada