Parametrized Metrical Task Systems

DOI10.4230/LIPICS.APPROX/RANDOM.2020.54MaRDI QIDQ6084418zbMATH OpenOpenAlexFDO

Authors Sébastien Bubeck, Yuval Rabani

Publication date 31 October 2023

Full work available at URL https://arxiv.org/abs/1904.03874

zbMATH Keywords

competitive analysismetrical task systemsonline computing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

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.

Cites work

• A decomposition theorem for task systems and bounds for randomized server problems
• A regularization approach to metrical task systems
• A tight bound on approximating arbitrary metrics by tree metrics
• An optimal on-line algorithm for metrical task system
• Better algorithms for unfair metrical task systems and applications
• Competitive algorithms for server problems
• Competitive paging algorithms
• scientific article; zbMATH DE number 437566 (Why is no real title available?)
• scientific article; zbMATH DE number 1559591 (Why is no real title available?)
• scientific article; zbMATH DE number 6472577 (Why is no real title available?)
• Metrical service systems with multiple servers
• Metrical task systems and the k-server problem on HSTs
• Metrical task systems on trees via mirror descent and unfair gluing
• On algorithm design for metrical task systems
• On convex body chasing
• Optimal Power-Down Strategies
• Randomized algorithms for metrical task systems
• Searching in the plane
• Traversing Layered Graphs Using the Work Function Algorithm
• Unfair problems and randomized algorithms for metrical task systems

Cited in

(3)

• Uniform metrical task systems with a limited number of states
• An optimal on-line algorithm for metrical task system
• Online Metric Algorithms with Untrusted Predictions

This page was built for publication: Parametrized Metrical Task Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6084418)