k-server via multiscale entropic regularization

© 2018 Copyright held by the owner/author(s). We present an O((log k)2)-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 underl...

Full description

Bibliographic Details
Main Authors: Bubeck, Sébastien, Cohen, Michael B., Lee, Yin Tat, Lee, James R., Mądry, Aleksander
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Association for Computing Machinery (ACM) 2021
Online Access:https://hdl.handle.net/1721.1/137726