Document Open Access Logo

Parametrized Metrical Task Systems

Authors Sébastien Bubeck, Yuval Rabani

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.54.pdf
  • Filesize: 426 kB
  • 14 pages

Document Identifiers

Author Details

Sébastien Bubeck
  • Microsoft Research, Redmond, WA, USA
Yuval Rabani
  • Hebrew University of Jerusalem, Israel

Funding

  • Rabani, Yuval: Research supported in part by ISF grants 956-15 and 2553-17. Part of this work was done while visiting Microsoft Research at Redmond.

Cite AsGet BibTex

Sébastien Bubeck and Yuval Rabani. Parametrized Metrical Task Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.54

Abstract

We consider parametrized versions of metrical task systems and metrical service systems, two fundamental models of online computing, where the constrained parameter is the number of possible distinct requests m. Such parametrization occurs naturally in a wide range of applications. Striking examples are certain power management problems, which are modeled as metrical task systems with m = 2. We characterize the competitive ratio in terms of the parameter m for both deterministic and randomized algorithms on hierarchically separated trees. Our findings uncover a rich and unexpected picture that differs substantially from what is known or conjectured about the unparametrized versions of these problems. For metrical task systems, we show that deterministic algorithms do not exhibit any asymptotic gain beyond one-level trees (namely, uniform metric spaces), whereas randomized algorithms do not exhibit any asymptotic gain even for one-level trees. In contrast, the special case of metrical service systems (subset chasing) behaves very differently. Both deterministic and randomized algorithms exhibit gain, for m sufficiently small compared to n, for any number of levels. Most significantly, they exhibit a large gain for uniform metric spaces and a smaller gain for two-level trees. Moreover, it turns out that in these cases (as well as in the case of metrical task systems for uniform metric spaces with m being an absolute constant), deterministic algorithms are essentially as powerful as randomized algorithms. This is surprising and runs counter to the ubiquitous intuition/conjecture that, for most problems that can be modeled as metrical task systems, the randomized competitive ratio is polylogarithmic in the deterministic competitive ratio.

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
Keywords
  • online computing
  • competitive analysis
  • metrical task systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Abernethy, P. L. Bartlett, N. Buchbinder, and I. Stanton. A regularization approach to metrical task systems. In Proc. of the 21st Int'l Conf. on Algorithmic Learning Theory, pages 270-284, 2010. Google Scholar
  2. J. Augustine, S. Irani, and C. Swamy. Optimal power-down strategies. SIAM J. Comput., 37(5):1499-1516, 2008. Google Scholar
  3. R. A. Baeza-Yates, J. C. Culberson, and G. J. E. Rawlins. Searching in the plane. Inf. Comput., 106(2):234-252, 1993. Google Scholar
  4. N. Bansal, N. Buchbinder, and J. Naor. Metrical task systems and the k-server problem on HSTs. In Proc. of the 37th Int'l Colloq. on Automata, Languages and Programming, pages 287-298, 2010. Google Scholar
  5. Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. of the 37th Ann. IEEE Symp. on Foundations of Computer Science, pages 184-193, 1996. Google Scholar
  6. Y. Bartal, A. Blum, C. Burch, and A. Tomkins. Polylog(n)-competitive algorithm for metrical task systems. In Proc. of the 29th Ann. ACM Symp. on Theory of Computing, pages 711-719, 1997. Google Scholar
  7. Y. Bartal, B. Bollobas, and M. Mendel. A Ramsey-type theorem for metric spaces and its applications for metrical task systems and related problems. In Proc. of the 42nd Ann. IEEE Symp. on Foundations of Computer Science, pages 396-405, 2001. Google Scholar
  8. Y. Bartal, M. Charikar, and P. Indyk. On page migration and other relaxed task systems. In Proc. of the 8th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 43-52, 1997. Google Scholar
  9. Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. In Proc. of the 35th Ann. ACM Symp. on Theory of computing, pages 463-472, June 2003. Google Scholar
  10. A. Blum and C. Burch. On-line learning and the metrical task system problem. In Proc. of the 10th Ann. Conf. on Computational Learning Theory, pages 45-53, 1997. Google Scholar
  11. A. Blum, H. J. Karloff, Y. Rabani, and M. E. Saks. A decomposition theorem for task systems and bounds for randomized server problems. SIAM J. Comput., 30(5):1624-1661, 2000. Google Scholar
  12. A. Borodin, N. Linial, and M. E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, 1992. Google Scholar
  13. S. Bubeck, M. B. Cohen, J. R. Lee, and Y.-T. Lee. Metrical task systems on trees via mirror descent and unfair gluing. In Proc. of the 30th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 89-97, 2019. Google Scholar
  14. W. R. Burley. Traversing layered graphs using the work function algorithm. J. Algorithms, 20(3):479-511, 1996. Google Scholar
  15. W. R. Burley and S. Irani. On algorithm design for metrical task systems. Algorithmica, 18(4):461-485, 1997. Google Scholar
  16. A. Chiplunkar and S. Vishwanathan. Metrical service systems with multiple servers. Algorithmica, 71(1):219-231, 2015. Google Scholar
  17. M. Chrobak and L. Larmore. Metrical service systems: deterministic strategies. Technical Report UCR-CS-93-1, UC Riverside, 1993. Google Scholar
  18. J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. Google Scholar
  19. E. Feuerstein. Uniform service systems with k servers. In Cláudio L. Lucchesi and Arnaldo V. Moura, editors, Proc. of LATIN'98: Theoretical Informatics, pages 23-32, 1998. Google Scholar
  20. A. Fiat, D. P. Foster, H. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan. Competitive algorithms for layered graph traversal. In Proc. of the 32nd Ann. IEEE Symp. of Foundations of Computer Science, pages 288-297, 1991. Google Scholar
  21. A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. E. Young. Competitive paging algorithms. J. Alg., 12(4):685-699, 1991. Google Scholar
  22. A. Fiat and M. Mendel. Better algorithms for unfair metrical task systems and applications. In Proc. of the 32nd Ann. ACM Symp. on Theory of computing, pages 725-734, May 2000. Google Scholar
  23. J. Friedman and N. Linial. On convex body chasing. Discrete & Computational Geometry, 9(3):293-321, 1993. Google Scholar
  24. S. Irani and S. Seiden. Randomized algorithms for metrical task systems. Theoretical Computer Science, 194(1):163-182, 1998. Google Scholar
  25. S. Irani, S. Shukla, and R. Gupta. Online strategies for dynamic power management in systems with multiple power-saving states. ACM Trans. Embed. Comput. Syst., 2(3):325-346, 2003. Google Scholar
  26. H. J. Karloff, Y. Rabani, and Y. Ravid. Lower bounds for randomized k-server and motion-planning algorithms. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, pages 279-288, May 1991. Google Scholar
  27. M. S. Manasse, L. A. McGeoch, and D. D. Sleator. Competitive algorithms for server problems. J. Algorithms, 11(2):208-230, 1990. Google Scholar
  28. C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. In Proc. of the 16th Int'l Colloq. on Automata, Languages and Programming, pages 610-620, 1989. Google Scholar
  29. H. Ramesh. On traversing layered graphs on-line. In Proc. of the 4th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 412-421, 1993. Google Scholar
  30. S. Seiden. Unfair problems and randomized algorithms for metrical task systems. Inf. Comput., 148(2):219-240, 1999. Google Scholar
  31. D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202-208, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact