More Web Proxy on the site http://driver.im/

research-article

Unfair Problems and Randomized Algorithms for Metrical Task Systems

Author:

Steve SeidenAuthors Info & Claims

Information and Computation, Volume 148, Issue 2

Pages 219 - 240

https://doi.org/10.1006/inco.1998.2744

Published: 01 February 1999 Publication History

Abstract

Borodin, Linial, and Saks introduced a general model for online systems calledmetrical task systems(1992,J. Assoc. Comput. Mach.39(4), 745 763). In this paper, the unfair two state problem, a natural generalization of the two state metrical task system problem, is studied. A randomized algorithm for this problem is presented, and it is shown that this algorithm is optimal. Using the analysis of the unfair two state problem, a proof of a decomposition theorem similar to that of Blum, Karloff, Rabani, and Saks (1992, “Proc. 33rd Symposium on Foundations of Computer Science,” pp. 197 207) is presented. This theorem allows one to design divide and conquer algorithms for specific metrical task systems. Our theorem gives the same bounds asymptotically, but it has less restrictive boundary conditions.

References

[1]

Y. Bartal, Probabalistic approximation of metric space and its algorithmic applications, 1996.

[2]

Bartal, Y. Blum, A, Burch, C. Tomkins, A. A polylog(n, Proc. 29th ACM Symposium on Theory of Computing, 711, 719

[3]

S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson, On the power of randomization in online algorithms, 1990.

[4]

Blum, A. Furst, M. Tomkins, A. What to do with your free time: On-line algorithms for infrequent request

[5]

A. Blum, H. Karloff, Y. Rabani, M. Saks, A decomposition theorem and bounds for randomized server problems, 1992.

[6]

A. Blum, P. Raghavan, B. Schieber, Navigating in unfamiliar geometric terrain, 1991.

[7]

A. Borodin, N. Linial, M. Saks, An optimal online algorithm for metrical task system, J. Assoc. Comput. Mach., 39 (1992) 745-763.

Digital Library

[8]

M. Chrobak, L.L. Larmore, Server problems and on-line games, 1991.

[9]

Chrobak, M. Noga, J.

[10]

Irani, S. Seiden, S. S. Randomized algorithms for metrical task systems, Theoret. Comput. Sci. 194, 163, 182

[11]

S. Irani, S.S. Seiden, Randomized algorithms for metrical task systems, 1995.

[12]

A. Karlin, M. Manasse, L. McGeoch, S. Owicki, Competitive randomized algorithms for nonuniform problems, Algorithmica, 11 (1994) 542-571.

Digital Library

[13]

A. Karlin, M. Manasse, L. Rudolph, D. Sleator, Competitive snoopy caching, Algorithmica, 3 (1988) 79-119.

Digital Library

[14]

C. Lund, N. Reingold, Linear programs for randomized on-line algorithms, 1994.

[15]

M. Manasse, L. McGeoch, D. Sleator, Competitive algorithms for server problems, J. Algorithms, 11 (1990) 208-230.

Digital Library

[16]

D. Sleator, R. Tarjan, Amortized efficiency of list update and paging rules, Com. ACM, 28 (1985) 202-208.

Digital Library

[17]

D. Sleator, R. Tarjan, Self adjusting binary search trees, J. Assoc. Comput. Mach., 32 (1985) 652-686.

Digital Library

[18]

J. Westbrook, Randomized algorithms for multiprocessor page migration, 1992.

Cited By

Bubeck SCoester CRabani YSaha BServedio R(2023)The Randomized 𝑘-Server Conjecture Is False!Proceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585132(581-594)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585132
Bubeck SCohen MLee JLee YChan T(2019)Metrical task systems on trees via mirror descent and unfair gluingProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310441(89-97)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310441
Coté AMeyerson APoplawski LLadner RDwork C(2008)Randomized k-server on hierarchical binary treesProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374411(227-234)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374411
Show More Cited By

Index Terms

Unfair Problems and Randomized Algorithms for Metrical Task Systems
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation

Recommendations

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems

A lower bound of $\Omega(\sqrt{\log k / \log \log k})$ is proved for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (having at least k+1 points) and ...
Better Algorithms for Unfair Metrical Task Systems and Applications

Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online ...
Metrical task systems on trees via mirror descent and unfair gluing
SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

We consider metrical task systems on tree metrics, and present an O(depthxlog n)-competitive randomized algorithm based on the mirror descent framework introduced in our prior work on the k-server problem. For the special case of hierarchically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 148, Issue 2

Feb. 1, 1999

115 pages

ISSN:0890-5401

Editor:
Albert R. Meyer
Massachusetts Institute of Technology, Cambridge

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 1999

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bubeck SCoester CRabani YSaha BServedio R(2023)The Randomized 𝑘-Server Conjecture Is False!Proceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585132(581-594)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585132
Bubeck SCohen MLee JLee YChan T(2019)Metrical task systems on trees via mirror descent and unfair gluingProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310441(89-97)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310441
Coté AMeyerson APoplawski LLadner RDwork C(2008)Randomized k-server on hierarchical binary treesProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374411(227-234)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374411
Bartal YBollobás BMendel M(2006)Ramsey-type theorems for metric spaces with applications to online problemsJournal of Computer and System Sciences10.1016/j.jcss.2005.05.00872:5(890-921)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1016/j.jcss.2005.05.008
Fleischer RGłazek WSeiden S(2004)New results for online page replicationTheoretical Computer Science10.1016/j.tcs.2004.05.017324:2-3(219-251)Online publication date: 20-Sep-2004
https://dl.acm.org/doi/10.1016/j.tcs.2004.05.017
Seiden S(2002)A General Decomposition Theorem for the k-Server ProblemInformation and Computation10.1006/inco.2002.3144174:2(193-202)Online publication date: 1-May-2002
https://dl.acm.org/doi/10.1006/inco.2002.3144
Fiat AMendel MYao FLuks E(2000)Better algorithms for unfair metrical task systems and applicationsProceedings of the thirty-second annual ACM symposium on Theory of computing10.1145/335305.335408(725-734)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/335305.335408
Seiden SYao FLuks E(2000)A guessing game and randomized online algorithmsProceedings of the thirty-second annual ACM symposium on Theory of computing10.1145/335305.335385(592-601)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/335305.335385
Blum ABurch C(2000)On-line Learning and the Metrical Task System ProblemMachine Language10.1023/A:100762183264839:1(35-58)Online publication date: 1-Apr-2000
https://dl.acm.org/doi/10.1023/A%3A1007621832648
Blum ABurch CKalai A(1999)Finely-Competitive PagingProceedings of the 40th Annual Symposium on Foundations of Computer Science10.5555/795665.796507Online publication date: 17-Oct-1999
https://dl.acm.org/doi/10.5555/795665.796507
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents