Making commitments in the face of uncertainty

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract)

Full text

Pdf (1.31 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: 519 - 530

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Baruch Awerbuch	Johns Hopkins University and Lab. for Computer Science, MIT
Yossi Azar	Department of Computer Science, Tel-Aviv University, Israel
Amos Fiat	Department of Computer Science, Tel-Aviv University, Israel
Tom Leighton	Mathematics Department and Lab for Computer Science, MIT

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 32, Citation Count: 25

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.238000 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.

	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
	ABF93	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]
	ABM93	Yossi Azar , Andrei Z. Broder , Mark S. Manasse, On-line choice of on-line algorithms, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.432-440, January 25-27, 1993, Austin, Texas, United States
	AGH94	Sudhanshu Aggarwal , Juan A. Garay , Amir Herzberg, Adaptive video on demand, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.402, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198189]
	BCLR95	S. Bhatt, F. Chung, T. Leighton, and A. Rosenberg. Optimal strategies for stealing cycles. Unpublished manuscript, 1995.
	BL94	R.D. Blumofe and C.E. Leiserson. Scheduling Multithreaded Computations by Work Stealing. In Proc. of the 35th Ann. IEEE Syrup. on Foundations of Computer Science, pages 356-368, November 1994.
	CEL93	J. Cooperstock, R. EI-Yaniv, T. Leighton. The Statistical Adversary Allows Online Foreign Exchange with no Risk. Proceedings of SODA '95.
	CV92	B. Chandra and S. Vishwanathan. Constructing Reliable Communication Networks of Small Weight On-line. Journal of Algorithms, 1992.
	EFKT92	R. El-Yaniv, A. Fiat, R. Karp, and G. Turpin. Competitive Analsys of Financial Games. In Proc. of the 33th Ann. IEEE Syrup. on Foundations o} Computer Science, pages 327-333, October 1992.
	EK93	R. Ei-Yaniv and R. Karp. The Mortage Problem. In Proc. of the ~nd Ann. Israeli Syrup. on Theoretical Computer Science, May 1993.
	FKT89	U. Faigle , W. Kern , G. Turan, On the performance of on-line algorithms for partition problems, Acta Cybernetica, v.9 n.2, p.107-119, 1989
	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
	Irani90	S. Irani. Coloring Inductive Graphs On-Line. In Proc. of the 31st Ann. IEEE Syrup. on Foundations of Computer Science, pages 470-479, October 1990.
	IW91	M. Imase and B.M. Waxman. Dynamic Steiner Tree Problem. In SIAM Journal on Discrete Mathematics, 4(3):369-384, August 1991.
	KP94	Bala Kalyanasundaram , Kirk R. Pruhs, Fault-tolerant scheduling, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.115-124, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195115]
	KMRS88	A.R. Karlin, M.S. Manasse, L. Rudolph, and D.D. Sleator. Competitive Snoopy Caching. In Algorithmica, 3(1):79-119, 1988.
	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]
	LT94	R. Lipton, Online interval scheduling, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.302-311, January 23-25, 1994, Arlington, Virginia, United States
	ST85a	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]
	ST85b	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
	Vish90	S. Vishwanathan. Randomized Online Graph Coloring. In Proc. of the 31st Ann. IEEE Syrup. on Foundations o} Computer Science, October 1990.
	WY93	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 25

	Ran El-Yaniv, Competitive solutions for online financial problems, ACM Computing Surveys (CSUR), v.30 n.1, p.28-69, March 1998
	T. S. Jayram , Tracy Kimbrel , Robert Krauthgamer , Baruch Schieber , Maxim Sviridenko, Online server allocation in a server farm via benefit task systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.540-549, July 2001, Hersonissos, Greece
	Arnold L. Rosenberg, Optimal Schedules for Cycle-Stealing in a Network of Workstations with a Bag-of-Tasks Workload, IEEE Transactions on Parallel and Distributed Systems, v.13 n.2, p.179-191, February 2002
	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
	Michael Mitzenmacher, How useful is old information (extended abstract)?, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.83-91, August 21-24, 1997, Santa Barbara, 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
	Baruch Awerbuch, Maximizing gross network product (GNP): resource management on the GII, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	Andrei Broder , Michael Mitzenmacher, Optimal plans for aggregation, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Baruch Awerbuch , Tripurari Singh, Online algorithms for selective multicast and maximal dense trees, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.354-362, May 04-06, 1997, El Paso, Texas, United States
	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
	Noga Alon , Baruch Awerbuch , Yossi Azar, The online set cover problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Reuven Bar-Yehuda , Magnús M. Halldórsson , Joseph (Seffi) Naor , Hadas Shachnai , Irina Shapira, Scheduling split intervals, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.732-741, January 06-08, 2002, San Francisco, California
	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
	Arnold L. Rosenberg, Optimal schedules for data-parallel cycle-stealing in networks of workstations (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.22-29, July 09-13, 2000, Bar Harbor, Maine, United States
	Susanne Albers , Moses Charikar , Michael Mitzenmacher, Delayed information and action in on-line algorithms, Information and Computation, v.170 n.2, p.135-152, November 1, 2001
	Amotz Bar-Noy , Juan A. Garay , Amir Herzberg, Sharing video on demand, Discrete Applied Mathematics, v.129 n.1, p.3-30, 15 June 2003
	Sandeep N. Bhatt , Fan R. K. Chung , F. Thomson Leighton , Arnold L. Rosenberg, On Optimal Strategies for Cycle-Stealing in Networks of Workstations, IEEE Transactions on Computers, v.46 n.5, p.545-557, May 1997
	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
	Michael Dahlin, Interpreting Stale Load Information, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1033-1047, October 2000
	Yossi Azar , Avrim Blum , Yishay Mansour, Combining online algorithms for rejection and acceptance, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Noga Alon , Yossi Azar , Shai Gutner, Admission control to minimize rejections and online set cover with repetitions, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Piotr Berman , Bhaskar DasGupta, Approximating the online set multicover problems via randomized winnowing, Theoretical Computer Science, v.393 n.1-3, p.54-71, March, 2008
	Jose Luis Bosque , Luis Pastor, A Parallel Computational Model for Heterogeneous Clusters, IEEE Transactions on Parallel and Distributed Systems, v.17 n.12, p.1390-1400, December 2006
	Anne Benoit , Mourad Hakem , Yves Robert, Contention awareness and fault-tolerant scheduling for precedence constrained tasks in heterogeneous systems, Parallel Computing, v.35 n.2, p.83-108, February, 2009
	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