Better algorithms for unfair metrical task systems and applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Better algorithms for unfair metrical task systems and applications

Full text

Pdf (1.06 MB)

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: 725 - 734

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Amos Fiat	Dept. of Computer Science, Tel-Aviv University
Manor Mendel	Dept. of Computer Science, Tel-Aviv University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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.335408 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	Dimitris Achlioptas , Marek Chrobak , John Noga, Competive Analysis of Randomized Paging Algorithms, Proceedings of the Fourth Annual European Symposium on Algorithms, p.419-430, September 25-27, 1996
	2	Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
	3	Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
	4	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]
	5	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]
	6	S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in onlille algorithms. Algorithmica, 11(1):2-14, jau. 1994.
	7	Avrim Blum , Carl Burch, On-line learning and the metrical task system problem, Proceedings of the tenth annual conference on Computational learning theory, p.45-53, July 06-09, 1997, Nashville, Tennessee, United States [doi>10.1145/267460.267475]
	8	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
	9	A. Blum, M. L. Furst, and A. Tomkins. What to do with your free time: algorithms for infrequeat requests and randomized weighted caching, manuscript, Apr. 1996.
	10	A. Blurn, H. Karloff, Y. Rabani, and M. Saks. A decomposition theorem and lower bounds for randomized server problems. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 197-207, 1992.
	11	A. Blum, H. Karloff, Y. Rabmfi, and M. Saks. A decomposition theorem and bounds for randomized server problems, manuscript, Feb. 1999. preliminary version appeared in {10}.
	12	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]
	13	M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.291-300, January 22-24, 1990, San Francisco, California, United States
	14	M. Chrobak and L. L. Larmore. The server problem and on-line games. In L. A. McGeoch a~ld D. D. Sleator, editors, On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 11-64, Feb. 1991.
	15	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]
	16	Sandy Irani , Steve Seiden, Randomized algorithms for metrical task systems, Theoretical Computer Science, v.194 n.1-2, p.163-182, March 10, 1998 [doi>10.1016/S0304-3975(97)00006-6]
	17	A. Karlin, M. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 3(1):79- 119, 1988.
	18	Howard Karloff , Yuval Rabani , Yiftach Ravid, Lower Bounds for Randomized $k$-Serverand Motion-Planning Algorithms, SIAM Journal on Computing, v.23 n.2, p.293-312, April 1994 [doi>10.1137/S0097539792224838]
	19	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
	20	L. McGeoch and D. Sleator. A strongly competitive randomized paging algorithm. J. Algorithms, 6:816- 825, 1991.
	21	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]
	22	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]
	23	N. Young. The k-server dual mid loose competitiveness for paging. Algorithmica, 11(6):525-541, June 1994.
	24	Neal E. Young, On-line file caching, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.82-86, January 25-27, 1998, San Francisco, California, United States

CITED BY 6

	Steven S. Seiden, A general decomposition theorem for the k-server problem, Information and Computation, v.174 n.2, p.193-202, May 1 2002
	Sandeep K. S. Gupta , Goran Konjevod , Georgios Varsamopoulos, A theoretical study of optimization techniques used in registration area based location management: models and online algorithms, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Steven S. Seiden, A guessing game and randomized online algorithms, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.592-601, May 21-23, 2000, Portland, Oregon, United States
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004
	Yair Bartal , Manor Mendel, Multi-embedding and path approximation of metric spaces, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland