On-line algorithms for Steiner tree problems (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line algorithms for Steiner tree problems (extended abstract)

Full text

Pdf (1.27 MB)

Source

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

El Paso, Texas, United States

Pages: 344 - 353

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Piotr Berman	Penn State University, University Park, PA
Chris Coulston	Penn State University, University Park, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 58, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/258533.258618 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	Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
	3	Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.164-173, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167142]
	4	B. Awerbuch, and D. Peleg. Network synchronization with polylogrithmic overhead, Proc. 31st FOCS, pp. 514-532, 1990.
	5	Y. Bartal. Competitive Analysis of Distributed On-line Problems m Distributed paging, Ph.D. Thesis. Tel-Aviv University, Dept. of Computer Science. 1994.
	6	Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
	7	M. Imaze and B.M. Waxman. Dynamic Steiner tree problem, SIAM J. on Discrete Mathematics, vol. 4, num. 3, pp.369-184, August 199 I.
	8	A. Kahng and G. Robins. On Optimal Interconnects for VLSI, Kluwer Academic Publishers, 1995.
	9	Carsten Lund , Nick Reingold , Jeffery Westbrook , Dicky C. K. Yan, On-Line Distributed Data Management, Proceedings of the Second Annual European Symposium on Algorithms, p.202-214, September 26-28, 1994
	10	S. Rao, P. Sadayappan, E Hwang and P. Shor. The Rectilinear Steiner Arborescence Problem, Algorithmica, 1992, pp. 277- 288.
	11	Jeffery Westbrook , Dicky C. K. Yan, Greedy Algorithms for the On-Line Steiner Tree and Generalized Steiner Problems, Proceedings of the Third Workshop on Algorithms and Data Structures, p.622-633, August 11-13, 1993

CITED BY 12

	Moses Charikar , Dan Halperin , Rajeev Motwani, The dynamic servers problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.410-419, January 25-27, 1998, San Francisco, California, United States
	Noga Alon , Baruch Awerbuch , Yossi Azar , Niv Buchbinder , Joseph (Seffi) Naor, A general approach to online network optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Moses Charikar , Joseph Naor , Baruch Schieber, Resource optimization in QoS multicast routing of real-time multimedia, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.340-348, April 2004
	Adam Meyerson, Online algorithms for network design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Theoretical Computer Science, v.324 n.2-3, p.313-324, 20 September 2004
	Noga Alon , Baruch Awerbuch , Yossi Azar , Niv Buchbinder , Joseph (Seffi) Naor, A general approach to online network optimization problems, ACM Transactions on Algorithms (TALG), v.2 n.4, p.640-660, October 2006
	Roee Engelberg , Joseph (Seffi) Naor, Equilibria in online games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.149-158, January 07-09, 2007, New Orleans, Louisiana
	Xiuzhen Cheng , Bhaskar Dasgupta , Bing Lu, Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem, Journal of Global Optimization, v.21 n.4, p.385-396, December 2001
	Spyros Angelopoulos, Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.248-257, January 07-09, 2007, New Orleans, Louisiana
	Niv Buchbinder , Joseph (Seffi) Naor, Online Primal-Dual Algorithms for Covering and Packing, Mathematics of Operations Research, v.34 n.2, p.270-286, May 2009
	Anupam Gupta , Ravishankar Krishnaswamy , R. Ravi, Online and stochastic survivable network design, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Niv Buchbinder , Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal: Dual Approach, Foundations and Trends® in Theoretical Computer Science, v.3 n.2$#8211;3, p.93-263, February 2009