A guessing game and randomized online algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A guessing game and randomized online algorithms

Full text

Pdf (928 KB)

Source

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

Portland, Oregon, United States

Pages: 592 - 601

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Steven S. Seiden

Department of Computer Science, 298 Coates Hall, Louisiana State University, Baton Rouge, LA and Max-Planck-Institut for Computer Science

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 45, Citation Count: 11

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/335305.335385 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	Susanne Albers , Hisashi Koga, New on-line algorithms for the page replication problem, Journal of Algorithms, v.27 n.1, p.75-96, April 1998 [doi>10.1006/jagm.1997.0906]
	2	Yair Bartal , Avrim Blum , Carl Burch , Andrew Tomkins, A polylog(n)-competitive algorithm for metrical task systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.711-719, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258667]
	3	S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in online algorithms. Algorithmica, 11(1):2-14, Jan 1994.
	4	D. L. Black and D. D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989.
	5	Avrim Blum , Carl Burch , Adam Kalai, Finely-Competitive Paging, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.450, October 17-18, 1999
	6	A. Borodin , R. El-Yaniv, On Randomization In Online Computation, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.226, June 24-27, 1997
	7	Allan Borodin , Ran El-Yaniv, On randomization in on-line computation, Information and Computation, v.150 n.2, p.244-267, May 1, 1999 [doi>10.1006/inco.1998.2775]
	8	Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992 [doi>10.1145/146585.146588]
	9	C. Chekuri , R. Motwani , B. Natarajan , C. Stien, Approximation techniques for average completion time scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 05-07, 1997, New Orleans, Louisiana, United States
	10	B. Chen and A. Vestjens. Scheduling on identical machines: How good is LPT in an online setting? Operations Research Letters, 21(4):165-169, Nov 1997.
	11	Daniel R. Dooly , Sally A. Goldman , Stephen D. Scott, TCP dynamic acknowledgment delay (extended abstract): theory and practice, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.389-398, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276792]
	12	Amos Fiat , Manor Mendel, Better algorithms for unfair metrical task systems and applications, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.725-734, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335408]
	13	Rudolf Fleischer, On The Bahncard Problem, Proceedings of the 4th Annual International Conference on Computing and Combinatorics, p.65-74, August 12-14, 1998
	14	R. Fleischer and S. S. Selden. Page replication-- Variations on a theme. Manuscript, 1999.
	15	Han Hoogeveen , Arjen P. A. Vestjens, Optimal On-Line Algorithms for Single-Machine Scheduling, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.404-414, June 03-05, 1996
	16	Csanád Imreh , John Noga, Scheduling with Machine Cost, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.168-176, August 08-11, 1999
	17	A. Karlin, M. Manasse, L. McGeoch, and S. Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6):542-571, Jun 1994.
	18	A. Karlin, M. Manasse, L. Rudolph, and D. Sleator. Competitive snoopy caching. Algorithmica, 3(1):79- 119, 1988.
	19	J. Noga. Unpublished manuscript, Jun 1999.
	20	John Noga , Steven S. Seiden, Scheduling Two Machines with Release Times, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.391-399, June 09-11, 1999
	21	S. S. Selden. Randomized online scheduiing with delivery times. Journal of Combinatorial Optimization, 3(4):399-416, Dec 1999.
	22	Steve Seiden, Unfair problems and randomized algorithms for metrical task systems, Information and Computation, v.148 n.2, p.219-240, Feb. 1, 1999 [doi>10.1006/inco.1998.2744]
	23	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]
	24	L. Stougie and A. P. A. Vestjens. Randomized on-line scheduling: How low can't you go? Manuscript, 1997.
	25	A. P. A. Vestjens. On-line Machine Scheduling. PhD thesis, Eindhoven University of Technology, The Netherlands, 1997.
	26	J. Von Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1st edition, 1944.
	27	A. C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, pages 222-227, 1977.

CITED BY 11

	Anna R. Karlin , Claire Kenyon , Dana Randall, Dynamic TCP acknowledgement and other stories about e/(e-1), Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.502-509, July 2001, Hersonissos, Greece
	Peter Damaschke, Two short notes on the on-line travelling salesman: handling times and lookahead, Theoretical Computer Science, v.289 n.1, p.845-852, 23 October 2002
	Susanne Albers , Helge Bals, Dynamic TCP acknowledgement: penalizing long delays, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Jens S. Frederiksen , Kim S. Larsen , John Noga , Patchrawat Uthaisombut, Dynamic TCP acknowledgment in the LogP model, Journal of Algorithms, v.48 n.2, p.407-428, September 2003
	Sven O. Krumke , Willem E. de Paepe , Diana Poensgen , Leen Stougie, News from the online traveling repairman, Theoretical Computer Science, v.295 n.1-3, p.279-294, 24 February 2003
	Leah Epstein , Alex Kesselman, On the remote server problem or more about TCP acknowledgments, Theoretical Computer Science, v.369 n.1, p.285-299, 15 December 2006
	J. Nagy-György , Cs. Imreh, Online scheduling with machine cost and rejection, Discrete Applied Mathematics, v.155 n.18, p.2546-2554, November, 2007
	Hisashi Koga, Dynamic TCP acknowledgment with sliding window, Theoretical Computer Science, v.410 n.8-10, p.914-925, March, 2009
	Yi-Wei Jiang , Yong He, Semi-online algorithms for scheduling with machine cost, Journal of Computer Science and Technology, v.21 n.6, p.984-988, November 2006
	Irene Fink , Sven O. Krumke , Stephan Westphal, New lower bounds for online k-server routing problems, Information Processing Letters, v.109 n.11, p.563-567, May, 2009
	Cs. Imreh, Online scheduling with general machine cost functions, Discrete Applied Mathematics, v.157 n.9, p.2070-2077, May, 2009

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures; Sequencing and scheduling

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE
I.2.8 Problem Solving, Control Methods, and Search
Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification

Collaborative Colleagues:

Steven S. Seiden: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player