Lower bounds for on-line graph problems with application to on-line circuit and optical routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for on-line graph problems with application to on-line circuit and optical routing

Full text

Pdf (1.09 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 531 - 540

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Yair Bartal	International Computer Science Institute, Berkeley
Amos Fiat	Department of Computer Science, Tel Aviv University, Tel Aviv
Stefano Leonardi	International Computer Science Institute (Berkeley) & Dipartimento di Informatica Sistemistica, Universitàà di Roma 'La Sapienza'

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 20

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/237814.238001 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.

	ABC+94	Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing and scheduling algorithms for optical networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.412-423, January 23-25, 1994, Arlington, Virginia, United States
	AAP93	B. Awerbuch, Y. Azar and S. Plotkin. Throughput Competitive On-line Routing. In Proc. of the 3~th Annual Syrup. on Foundations of Computer Science, November 1993.
	ABFR94	Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
	AGLR94	B. Awerbuch, R. Gawlick, F.T. Leighton and Y. R~bani. On-line Admission Control and Circuit Routing for High Performance Computing and Communication. In Proc. of the 35th Annual Syrup. on Foundations of Computer Science, 1994.
	BH92	Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
	BH93	R.A. Barry and P.A. Humbler. On the Number of Wavelengths and Switches in All Optical Networks. IEEE Trans. Comm., 1993.
	GG92	Juan A. Garay , Inder S. Gopal, Call preemption in communication networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.1043-1050, May 1992, Florence, Italy
	GGKMY93	J. Garay, I.S. Gopal, S. Kutten, Y. Mansour and M. Yung. Efficient On-line Call Control Algorithms. In Proc. ~nd Israel Syrup. on Theory of Computing and Systems, pages 285-293, june 1993.
	Hal94	M.M. HalldSrsson. Approximation via partitioning. Manuscript, 1994.
	HS92	Magnús M. Halldórsson , Márió Szegedy, Lower bounds for on-line graph coloring, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.211-216, September 1992, Orlando, Florida, United States
	I90	S. Irani. Coloring inductive Graphs On-Line. In Proc. of the 31st Ann. iEEE Syrup. on Foundations o/Computer Science, pages 470-479, October 1990.
	KS95	V. Kapoulas , P. Spirakis, Randomized competitive algorithms for admission control in general networks, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.253, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224992]
	KVV90	R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
	KT95	J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
	LY93a	Carsten Lund , Mihalis Yannakakis, The Approximation of Maximum Subgraph Problems, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.40-51, July 05-09, 1993
	LY93b	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	P92	R.K. Pank~y. Architectures for Linear Light-wave Networks. PhD thesis, MIT, 1992.
	RU94	Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195119]
	ST85	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	V90	S. Vishwanathan. Randomized On-line Graph Coloring, InProc. o/ the 31st iEEE Annual Syrup. on Foundations o/Computer Science, pp. 464-469, 1990.
	Y77	A.C. Yao. Probabilistic Computations: Towards a Unified Measure of Complexity. In Proc. o/the 17th Annual Syrup. on Foundations o/Computer Science, pp. 222-227, 1977.

CITED BY 20

	Magnús M. Halldórsson, Online coloring known graphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.917-918, January 17-19, 1999, Baltimore, Maryland, United States
	Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	Ashish Goel , Monika R. Henzinger , Serge Plotkin, Online througput-competitive algorithm for multicast routing and admission control, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.97-106, January 25-27, 1998, San Francisco, California, United States
	Haim Kaplan , Mario Szegedy, On-line complexity of monotone set systems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.507-516, January 17-19, 1999, Baltimore, Maryland, United States
	Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.189-197, May 01-04, 1999, Atlanta, Georgia, United States
	Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 17-19, 1999, Baltimore, Maryland, United States
	Luca Becchetti , Miriam Di Ianni , Alberto Marchetti-Spaccamela, Approximation algorithms for routing and call scheduling in all-optical chains and rings, Theoretical Computer Science, v.287 n.2, p.429-448, 28 September 2002
	Monika R. Henzinger , Stefano Leonardi, Scheduling multicasts on unit-capacity trees and meshes, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.438-447, January 17-19, 1999, Baltimore, Maryland, United States
	Monika R. Henzinger , Stefano Leonardi, Scheduling multicasts on unit-capacity trees and meshes, Journal of Computer and System Sciences, v.66 n.3, p.567-611, May 2003
	Ioannis Caragiannis , Christos Kaklamanis , Evi Papaioannou, Efficient on-line communication in cellular networks, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.46-53, July 09-13, 2000, Bar Harbor, Maine, United States
	Stefano Leonardi , Alberto Marchetti-Spaccamela , Alessio Presciutti , Adi Rosén, On-line randomized call control revisited, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.323-332, January 25-27, 1998, San Francisco, California, United States
	Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Journal of Algorithms, v.48 n.2, p.314-332, September 2003
	Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Journal of Scheduling, v.6 n.2, p.113-129, March/April 2003
	Ashish Goel , Monika R. Henzinger , Serge Plotkin, An online throughput-competitive algorithm for multicast routing and admission control, Journal of Algorithms, v.55 n.1, p.1-20, April 2005
	Harald Räcke , Adi Rosén, Distributed online call control on general networks, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Petr Kolman , Christian Scheideler, Simple on-line algorithms for the maximum disjoint paths problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.38-47, July 2001, Crete Island, Greece
	Amitabha Bagchi , Amitabh Chaudhary , Petr Kolman, Short length Menger's theorem and reliable optical routing, Theoretical Computer Science, v.339 n.2, p.315-332, 12 June 2005
	E. G. Coffman, Jr. , Anja Feldmann , Nabil Kahale , Bjorn Poonen, COMPUTING CALL ADMISSION CAPACITIES IN LINEAR NETWORKS, Probability in the Engineering and Informational Sciences, v.13 n.4, p.387-406, October 1999
	Keqin Li, Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks, Journal of Experimental Algorithmics (JEA), 12, June 2008
	Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, Journal of Computer and System Sciences, v.74 n.7, p.1147-1159, November, 2008