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...

全面介绍

书目详细资料
Main Authors: Bubeck, Sébastien, Cohen, Michael B., Lee, Yin Tat, Lee, James R., Mądry, Aleksander
其他作者: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
格式: 文件
语言:English
出版: Association for Computing Machinery (ACM) 2021
在线阅读:https://hdl.handle.net/1721.1/137726