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: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137726 |
| _version_ | 1826194406049316864 |
|---|---|
| author | Bubeck, Sébastien Cohen, Michael B. Lee, Yin Tat Lee, James R. Mądry, Aleksander |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bubeck, Sébastien Cohen, Michael B. Lee, Yin Tat Lee, James R. Mądry, Aleksander |
| author_sort | Bubeck, Sébastien |
| collection | MIT |
| description | © 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 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)2 log n)-competitive algorithm on any n-point metric space. We give a new dynamic HST embedding that yields an O((log k)3 log ∆)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most ∆. |
| first_indexed | 2024-09-23T09:55:37Z |
| format | Article |
| id | mit-1721.1/137726 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:55:37Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1377262023-04-14T18:23:01Z k-server via multiscale entropic regularization 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 Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 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 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)2 log n)-competitive algorithm on any n-point metric space. We give a new dynamic HST embedding that yields an O((log k)3 log ∆)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most ∆. 2021-11-08T17:42:06Z 2021-11-08T17:42:06Z 2018-06 2019-06-13T17:15:41Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137726 Bubeck, Sébastien, Cohen, Michael B., Lee, Yin Tat, Lee, James R. and Mądry, Aleksander. 2018. "k-server via multiscale entropic regularization." en 10.1145/3188745.3188798 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Bubeck, Sébastien Cohen, Michael B. Lee, Yin Tat Lee, James R. Mądry, Aleksander k-server via multiscale entropic regularization |
| title | k-server via multiscale entropic regularization |
| title_full | k-server via multiscale entropic regularization |
| title_fullStr | k-server via multiscale entropic regularization |
| title_full_unstemmed | k-server via multiscale entropic regularization |
| title_short | k-server via multiscale entropic regularization |
| title_sort | k server via multiscale entropic regularization |
| url | https://hdl.handle.net/1721.1/137726 |
| work_keys_str_mv | AT bubecksebastien kserverviamultiscaleentropicregularization AT cohenmichaelb kserverviamultiscaleentropicregularization AT leeyintat kserverviamultiscaleentropicregularization AT leejamesr kserverviamultiscaleentropicregularization AT madryaleksander kserverviamultiscaleentropicregularization |