k-server via multiscale entropic regularization

2017/11/03 by Bubeck, Sebastien, Cohen, Michael B., Lee, James R. +2 · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1711.01085

Abstract

We present an O((log k)²)-competitive randomized algorithm for the k-server problem on hierarchically separated trees (HSTs). This is the first o(k)-competitive randomized algorithm for which the competitive ratio is independent of the size of the underlying HST. Our algorithm is designed in the framework of online mirror descent where the mirror map is a multiscale entropy. When combined with Bartal's static HST embedding reduction, this leads to an O((log k)² log n)-competitive algorithm on any n-point metric space. We give a new dynamic HST embedding that yields an O((log k)³ log Δ)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most Δ.

Cited by

• A Learning Perspective on Random-Order Covering Problems
• Online 3-Taxi on General Metrics
• Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Related

• Fusible HSTs and the randomized k-server conjecture
• Metrical task systems on trees via mirror descent and unfair gluing
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• Pure entropic regularization for metrical task systems
• Unbounded lower bound for k-server against weak adversaries