On-line learning and the metrical task system problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line learning and the metrical task system problem

Full text

Pdf (1.47 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the tenth annual conference on Computational learning theory table of contents

Nashville, Tennessee, United States

Pages: 45 - 53

Year of Publication: 1997

ISBN:0-89791-891-6

Authors

Avrim Blum	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Carl Burch	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA

Sponsors

AT&T Labs :
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Vanderbilt University : Vanderbilt University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

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

	BBBT97	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]
	BKRS92	A. Blum, H. Karloff, Y. Rabani, and M. Saks. A decomposition theorem and lower bounds for randomized server problems. In Proc IEEE Symposium on Foundations of Computer Science, pages 197-207, 1992.
	BLS92	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]
	Chu94	Thomas H. Chung, Approximate methods for sequential decision making using expert advice, Proceedings of the seventh annual conference on Computational learning theory, p.183-189, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181097]
	Esk90	M. Eskicioglu. Process migration in distributed systems: A compatitive survey. Technical Report TR 90-3, University of Alberta, January 1990.
	FKL+91	Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
	FS95	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
	HW95	M. Herbster and M. Warmuth. Tracking the best expert. In Prvc International Conference on Machine Learning, pages 286-294. Morgan Kaufmann, 1995.
	IS95	Sandy Irani , Steven S. Seiden, Randomized Algorithms for Metrical Task Systems, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.159-170, August 16-18, 1995
	LW94	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	Sei96	S. Seiden. Unfair problems and randomized algorithms for metrical task systems. Manuscript, April 1996.

CITED BY 9

	Mark Herbster , Manfred K. Warmuth, Tracking the best regressor, Proceedings of the eleventh annual conference on Computational learning theory, p.24-31, July 24-26, 1998, Madison, Wisconsin, United States
	Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002
	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
	Rani Yaroshinsky , Ran El-Yaniv , Steven S. Seiden, How to Better Use Expert Advice, Machine Learning, v.55 n.3, p.271-309, June 2004
	Rudolf Fleischer , Włodzimierz Głazek , Steve Seiden, New results for online page replication, Theoretical Computer Science, v.324 n.2-3, p.219-251, 20 September 2004
	Mark Herbster , Manfred K. Warmuth, Tracking the Best Expert, Machine Learning, v.32 n.2, p.151-178, Aug. 1998
	Wolfgang Bein , Lawrence L. Larmore , John Noga, Uniform metrical task systems with a limited number of states, Information Processing Letters, v.104 n.4, p.123-128, November, 2007
	Peter A. Dinda, Design, Implementation, and Performance of an Extensible Toolkit for Resource Prediction in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.17 n.2, p.160-173, February 2006
	Michael Bowling , Manuela Veloso, Rational and convergent learning in stochastic games, Proceedings of the 17th international joint conference on Artificial intelligence, p.1021-1026, August 04-10, 2001, Seattle, WA, USA