2026-07-24T18:53:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15656 2024-03-06T10:55:52Z ddc:004 open_access

Multiscale Entropic Regularization for MTS on General Metric Spaces Ebrahimnejad, Farzam Lee, James R. Metrical task systems online algorithms metric embeddings convex optimization We present an O((log n)²)-competitive algorithm for metrical task systems (MTS) on any n-point metric space that is also 1-competitive for service costs. This matches the competitive ratio achieved by Bubeck, Cohen, Lee, and Lee (2019) and the refined competitive ratios obtained by Coester and Lee (2019). Those algorithms work by first randomly embedding the metric space into an ultrametric and then solving MTS there. In contrast, our algorithm is cast as regularized gradient descent where the regularizer is a multiscale metric entropy defined directly on the metric space. This answers an open question of Bubeck (Highlights of Algorithms, 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Farzam Ebrahimnejad and James R. Lee 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.60 urn:nbn:de:0030-drops-156568 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.60 eng https://creativecommons.org/licenses/by/4.0/legalcode