@inproceedings{MMS88,
  author = {Manasse, Mark S. and McGeoch, Lyle A. and Sleator, Daniel D.},
  title = {Competitive Algorithms for On-Line Problems},
  booktitle = {Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing},
  year = {1988}, pages = {322--333},
  doi = {10.1145/62212.62243},
  url = {https://doi.org/10.1145/62212.62243},
  note = {\href{https://doi.org/10.1145/62212.62243}{doi:10.1145/62212.62243}}
}
@article{MMS90,
  author = {Manasse, Mark S. and McGeoch, Lyle A. and Sleator, Daniel D.},
  title = {Competitive Algorithms for Server Problems},
  journal = {Journal of Algorithms},
  volume = {11}, number = {2}, pages = {208--230}, year = {1990},
  doi = {10.1016/0196-6774(90)90003-W},
  url = {https://doi.org/10.1016/0196-6774(90)90003-W},
  note = {\href{https://doi.org/10.1016/0196-6774(90)90003-W}{doi:10.1016/0196-6774(90)90003-W}}
}
@article{KP95,
  author = {Koutsoupias, Elias and Papadimitriou, Christos H.},
  title = {On the {$k$}-Server Conjecture},
  journal = {Journal of the ACM},
  volume = {42}, number = {5}, pages = {971--983}, year = {1995},
  doi = {10.1145/210118.210128},
  url = {https://doi.org/10.1145/210118.210128},
  note = {\href{https://doi.org/10.1145/210118.210128}{doi:10.1145/210118.210128}}
}
@article{FKLMSY91,
  author = {Fiat, Amos and Karp, Richard M. and Luby, Michael and McGeoch, Lyle A.
    and Sleator, Daniel D. and Young, Neal E.},
  title = {Competitive Paging Algorithms},
  journal = {Journal of Algorithms},
  volume = {12}, number = {4}, pages = {685--699}, year = {1991},
  doi = {10.1016/0196-6774(91)90041-V},
  url = {https://doi.org/10.1016/0196-6774(91)90041-V},
  note = {\href{https://doi.org/10.1016/0196-6774(91)90041-V}{doi:10.1016/0196-6774(91)90041-V}}
}
@article{MS91,
  author = {McGeoch, Lyle A. and Sleator, Daniel D.},
  title = {A Strongly Competitive Randomized Paging Algorithm},
  journal = {Algorithmica},
  volume = {6}, pages = {816--825}, year = {1991},
  doi = {10.1007/BF01759073},
  url = {https://doi.org/10.1007/BF01759073},
  note = {\href{https://doi.org/10.1007/BF01759073}{doi:10.1007/BF01759073}}
}
@article{KRR94,
  author = {Karloff, Howard and Rabani, Yuval and Ravid, Yiftach},
  title = {Lower Bounds for Randomized {$k$}-Server and Motion-Planning Algorithms},
  journal = {SIAM Journal on Computing},
  volume = {23}, number = {2}, pages = {293--312}, year = {1994},
  doi = {10.1137/S0097539792224838},
  url = {https://doi.org/10.1137/S0097539792224838},
  note = {\href{https://doi.org/10.1137/S0097539792224838}{doi:10.1137/S0097539792224838}}
}
@article{BKRS00,
  author = {Blum, Avrim and Karloff, Howard and Rabani, Yuval and Saks, Michael},
  title = {A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems},
  journal = {SIAM Journal on Computing},
  volume = {30}, number = {5}, pages = {1624--1661}, year = {2000},
  doi = {10.1137/S0097539799351882},
  url = {https://doi.org/10.1137/S0097539799351882},
  note = {\href{https://doi.org/10.1137/S0097539799351882}{doi:10.1137/S0097539799351882}}
}
@article{BBM06,
  author = {Bartal, Yair and Bollob{\'a}s, B{\'e}la and Mendel, Manor},
  title = {Ramsey-Type Theorems for Metric Spaces with Applications to Online Problems},
  journal = {Journal of Computer and System Sciences},
  volume = {72}, number = {5}, pages = {890--921}, year = {2006},
  doi = {10.1016/j.jcss.2005.05.008},
  url = {https://doi.org/10.1016/j.jcss.2005.05.008},
  note = {\href{https://doi.org/10.1016/j.jcss.2005.05.008}{doi:10.1016/j.jcss.2005.05.008}}
}
@article{BLMN05,
  author = {Bartal, Yair and Linial, Nathan and Mendel, Manor and Naor, Assaf},
  title = {On Metric {Ramsey}-Type Phenomena},
  journal = {Annals of Mathematics},
  volume = {162}, number = {2}, pages = {643--709}, year = {2005},
  doi = {10.4007/annals.2005.162.643},
  url = {https://doi.org/10.4007/annals.2005.162.643},
  note = {\href{https://doi.org/10.4007/annals.2005.162.643}{doi:10.4007/annals.2005.162.643}}
}
@inproceedings{Bartal96,
  author = {Bartal, Yair},
  title = {Probabilistic Approximation of Metric Spaces and Its Algorithmic Applications},
  booktitle = {Proceedings of the 37th Annual Symposium on Foundations of Computer Science},
  year = {1996}, pages = {184--193},
  doi = {10.1109/SFCS.1996.548477},
  url = {https://doi.org/10.1109/SFCS.1996.548477},
  note = {\href{https://doi.org/10.1109/SFCS.1996.548477}{doi:10.1109/SFCS.1996.548477}}
}
@inproceedings{Bartal98,
  author = {Bartal, Yair},
  title = {On Approximating Arbitrary Metrices by Tree Metrics},
  booktitle = {Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing},
  year = {1998}, pages = {161--168},
  doi = {10.1145/276698.276725},
  url = {https://doi.org/10.1145/276698.276725},
  note = {\href{https://doi.org/10.1145/276698.276725}{doi:10.1145/276698.276725}}
}
@article{FRT04,
  author = {Fakcharoenphol, Jittat and Rao, Satish and Talwar, Kunal},
  title = {A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics},
  journal = {Journal of Computer and System Sciences},
  volume = {69}, number = {3}, pages = {485--497}, year = {2004},
  doi = {10.1016/j.jcss.2004.04.011},
  url = {https://doi.org/10.1016/j.jcss.2004.04.011},
  note = {\href{https://doi.org/10.1016/j.jcss.2004.04.011}{doi:10.1016/j.jcss.2004.04.011}}
}
@inproceedings{CMP08,
  author = {Cot{\'e}, Aaron and Meyerson, Adam and Poplawski, Laura},
  title = {Randomized {$k$}-Server on Hierarchical Binary Trees},
  booktitle = {Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing},
  year = {2008}, pages = {227--234},
  doi = {10.1145/1374376.1374411},
  url = {https://doi.org/10.1145/1374376.1374411},
  note = {\href{https://doi.org/10.1145/1374376.1374411}{doi:10.1145/1374376.1374411}}
}
@inproceedings{BBN10,
  author = {Bansal, Nikhil and Buchbinder, Niv and Naor, Joseph (Seffi)},
  title = {Towards the Randomized {$k$}-Server Conjecture: A Primal-Dual Approach},
  booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms},
  year = {2010}, pages = {40--55},
  doi = {10.1137/1.9781611973075.5},
  url = {https://doi.org/10.1137/1.9781611973075.5},
  note = {\href{https://doi.org/10.1137/1.9781611973075.5}{doi:10.1137/1.9781611973075.5}}
}
@article{BBN12,
  author = {Bansal, Nikhil and Buchbinder, Niv and Naor, Joseph (Seffi)},
  title = {A Primal-Dual Randomized Algorithm for Weighted Paging},
  journal = {Journal of the ACM},
  year = {2012}, volume = {59}, number = {4}, pages = {19:1--19:24},
  doi = {10.1145/2339123.2339126},
  url = {https://doi.org/10.1145/2339123.2339126},
  note = {\href{https://doi.org/10.1145/2339123.2339126}{doi:10.1145/2339123.2339126}}
}
@article{BBMN15,
  author = {Bansal, Nikhil and Buchbinder, Niv and M{\k a}dry, Aleksander and Naor, Joseph (Seffi)},
  title = {A Polylogarithmic-Competitive Algorithm for the {$k$}-Server Problem},
  journal = {Journal of the ACM},
  year = {2015}, volume = {62}, number = {5}, pages = {40:1--40:49},
  doi = {10.1145/2783434},
  url = {https://doi.org/10.1145/2783434},
  eprint = {1110.1580}, archivePrefix = {arXiv},
  note = {\href{https://doi.org/10.1145/2783434}{doi:10.1145/2783434}.
    Section references are to the \href{https://madry.mit.edu/docs/kserver.pdf}{full author version}}
}
@inproceedings{BCLLM18,
  author = {Bubeck, S{\'e}bastien and Cohen, Michael B. and Lee, James R.
    and Lee, Yin Tat and M{\k a}dry, Aleksander},
  title = {{$k$}-Server via Multiscale Entropic Regularization},
  booktitle = {Proceedings of the Fiftieth Annual ACM SIGACT Symposium on Theory of Computing},
  year = {2018}, pages = {3--16},
  doi = {10.1145/3188745.3188798},
  url = {https://doi.org/10.1145/3188745.3188798},
  eprint = {1711.01085}, archivePrefix = {arXiv},
  note = {\href{https://doi.org/10.1145/3188745.3188798}{doi:10.1145/3188745.3188798}.
    Section references are to the full version, \href{https://arxiv.org/abs/1711.01085v1}{arXiv:1711.01085v1}}
}
@article{KLMN05,
  author = {Krauthgamer, Robert and Lee, James R. and Mendel, Manor and Naor, Assaf},
  title = {Measured Descent: A New Embedding Method for Finite Metrics},
  journal = {Geometric and Functional Analysis},
  year = {2005}, volume = {15}, number = {4}, pages = {839--858},
  doi = {10.1007/s00039-005-0527-6},
  url = {https://doi.org/10.1007/s00039-005-0527-6},
  note = {\href{https://doi.org/10.1007/s00039-005-0527-6}{doi:10.1007/s00039-005-0527-6}}
}
@inproceedings{BCR23,
  author = {Bubeck, S{\'e}bastien and Coester, Christian and Rabani, Yuval},
  title = {The Randomized {$k$}-Server Conjecture Is False!},
  booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing},
  year = {2023}, pages = {581--594},
  doi = {10.1145/3564246.3585132},
  url = {https://doi.org/10.1145/3564246.3585132},
  eprint = {2211.05753}, archivePrefix = {arXiv},
  note = {\href{https://doi.org/10.1145/3564246.3585132}{doi:10.1145/3564246.3585132}.
    Numbered references are to the full version,
    \href{https://arxiv.org/abs/2211.05753v2}{arXiv:2211.05753v2}, July 6, 2023}
}
@inproceedings{Lee18,
  author = {Lee, James R.},
  title = {Fusible {HSTs} and the Randomized {$k$}-Server Conjecture},
  booktitle = {Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science},
  year = {2018}, pages = {438--449},
  doi = {10.1109/FOCS.2018.00049},
  url = {https://doi.org/10.1109/FOCS.2018.00049},
  note = {\href{https://doi.org/10.1109/FOCS.2018.00049}{doi:10.1109/FOCS.2018.00049}.
    Section references are to \href{https://arxiv.org/abs/1711.01789v2}{arXiv:1711.01789v2},
    February 21, 2018. The general competitive-ratio claim was withdrawn
    in version 3, July 28, 2021; see the author's erratum},
  eprint = {1711.01789}, archivePrefix = {arXiv}
}
@misc{LeeErratum,
  author = {Lee, James R.},
  title = {Erratum: Fusible {HSTs} and the Randomized {$k$}-Server Conjecture},
  howpublished = {\url{https://homes.cs.washington.edu/~jrl/papers/kserver-erratum.html}},
  note = {Accessed October 3, 2026}
}
@misc{CKZ26,
  author = {Coester, Christian and Koutsoupias, Elias and Zbysi{\'n}ski, Marek},
  title = {The {$k$}-Server Conjecture Is True},
  year = {2026}, month = sep,
  eprint = {2609.15979}, archivePrefix = {arXiv},
  doi = {10.48550/arXiv.2609.15979},
  url = {https://doi.org/10.48550/arXiv.2609.15979},
  note = {\href{https://doi.org/10.48550/arXiv.2609.15979}{doi:10.48550/arXiv.2609.15979}. Version 1, September 14, 2026}
}
@article{Karamata32,
  author = {Karamata, Jovan},
  title = {Sur une in{\'e}galit{\'e} relative aux fonctions convexes},
  journal = {Publications math{\'e}matiques de l'Universit{\'e} de Belgrade},
  volume = {1}, pages = {145--148}, year = {1932},
  url = {https://elib.mi.sanu.ac.rs/files/journals/publ/1/11.pdf},
  note = {\href{https://elib.mi.sanu.ac.rs/files/journals/publ/1/11.pdf}{Original journal archive}}
}
@article{Bregman67,
  author = {Bregman, L. M.},
  title = {The Relaxation Method of Finding the Common Point of Convex Sets
    and Its Application to the Solution of Problems in Convex Programming},
  journal = {USSR Computational Mathematics and Mathematical Physics},
  volume = {7}, number = {3}, pages = {200--217}, year = {1967},
  doi = {10.1016/0041-5553(67)90040-7},
  url = {https://doi.org/10.1016/0041-5553(67)90040-7},
  note = {\href{https://doi.org/10.1016/0041-5553(67)90040-7}{doi:10.1016/0041-5553(67)90040-7}}
}
@incollection{Kuhn53,
  author = {Kuhn, Harold W.},
  title = {Extensive Games and the Problem of Information},
  editor = {Kuhn, Harold W. and Tucker, Albert W.},
  booktitle = {Contributions to the Theory of Games II},
  series = {Annals of Mathematics Studies}, volume = {28},
  publisher = {Princeton University Press},
  year = {1953}, pages = {193--216},
  doi = {10.1515/9781400881970-012},
  url = {https://doi.org/10.1515/9781400881970-012},
  note = {\href{https://doi.org/10.1515/9781400881970-012}{doi:10.1515/9781400881970-012}}
}
@inproceedings{Yao77,
  author = {Yao, Andrew Chi-Chih},
  title = {Probabilistic Computations: Toward a Unified Measure of Complexity},
  booktitle = {18th Annual Symposium on Foundations of Computer Science},
  year = {1977}, pages = {222--227},
  doi = {10.1109/SFCS.1977.24},
  url = {https://doi.org/10.1109/SFCS.1977.24},
  note = {\href{https://doi.org/10.1109/SFCS.1977.24}{doi:10.1109/SFCS.1977.24}}
}
@article{Tychonoff35,
  author = {Tychonoff, Andrei},
  title = {{\"U}ber einen {Funktionenraum}},
  journal = {Mathematische Annalen},
  volume = {111}, pages = {762--766}, year = {1935},
  doi = {10.1007/BF01472255},
  url = {https://doi.org/10.1007/BF01472255},
  note = {\href{https://doi.org/10.1007/BF01472255}{doi:10.1007/BF01472255}}
}

@book{Kelley55,
 author = {Kelley, John L.},
 title = {General Topology},
 publisher = {D. Van Nostrand Company},
 address = {New York},
 year = {1955},
 note = {Chapter~5, Theorem~13. Unabridged \href{https://store.doverpublications.com/products/9780486815442}{Dover republication}, 2017}
}

@inproceedings{CoesterCosson2026,
 author={Christian Coester and Romain Cosson},
 title={Randomized {$k$}-Server in Polynomial Time},
 booktitle={53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
 series={Leibniz International Proceedings in Informatics (LIPIcs)},
 volume={374},
 pages={65:1--65:20},
 year={2026},
 publisher={Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
 doi={10.4230/LIPIcs.ICALP.2026.65},
 url={https://doi.org/10.4230/LIPIcs.ICALP.2026.65},
 note={\href{https://doi.org/10.4230/LIPIcs.ICALP.2026.65}{doi:10.4230/LIPIcs.ICALP.2026.65}}
}