k-server problem

<h2 id="example">Example</h2>
To make the problem more concrete, imagine sending customer support technicians to customers when they have trouble with their equipment. In our example problem there are two technicians, Mary and Noah, serving three customers, in San Francisco, California; Washington, DC; and Baltimore, Maryland. As a k-server problem, the servers are the technicians, so k = 2 and this is a 2-server problem. Washington and Baltimore are 35 miles (56 km) apart, while San Francisco is 3,000 miles (4,800 km) away from both, and initially Mary and Noah are both in San Francisco.
Consider an algorithm for assigning servers to requests that always assigns the closest server to the request, and suppose that each weekday morning the customer in Washington needs assistance while each weekday afternoon the customer in Baltimore needs assistance, and that the customer in San Francisco never needs assistance. Then, our algorithm will assign one of the servers (say Mary) to the Washington area, after which she will always be the closest server and always be assigned to all customer requests. Thus, every day our algorithm incurs the cost of traveling between Washington and Baltimore and back, 70 miles (110 km). After a year of this request pattern, the algorithm will have incurred 20,500 miles (33,000 km) travel: 3,000 to send Mary to the East Coast, and 17,500 for the trips between Washington and Baltimore. On the other hand, an optimal adversary who knows the future request schedule could have sent both Mary and Noah to Washington and Baltimore respectively, paying 6,000 miles (9,700 km) of travel once but then avoiding any future travel costs. The competitive ratio of our algorithm on this input is 20,500/6,000 or approximately 3.4, and by adjusting the parameters of this example the competitive ratio of this algorithm can be made arbitrarily large.
Thus we see that always assigning the closest server can be far from optimal. On the other hand, it seems foolish for an algorithm that does not know future requests to send both of its technicians away from San Francisco, as the next request could be in that city and it would have to send someone back immediately. So it seems that it is difficult or impossible for a k-server algorithm to perform well relative to its adversary. However, for the 2-server problem, there exists an algorithm that always has a total travel distance of at most twice the adversary's distance.
The k-server conjecture states that similar solutions exist for problems with any larger number of technicians.

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Marek_Chrobak/YrLlChdY">Chrobak, Marek</a>; <a href="/facts/Lawrence_L._Larmore/r4vy1vqk">Larmore, Lawrence L.</a> (1991). "An optimal on-line algorithm for K-servers on trees". SIAM Journal on Computing. 20 (1): 144–148. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.2395">10.1.1.53.2395</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0220008">10.1137/0220008</a>.</li></ul>
<ul><li>Fiat, A.; Rabani, Y.; Ravid, Y. (1990). "Competitive k-server algorithms". Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science. pp. 454–463.</li></ul>
<ul><li>Koutsoupias, Elias; <a href="/facts/Christos_Papadimitriou/rXflR4or">Papadimitriou, Christos H.</a> (1995). "On the k-server conjecture". Journal of the ACM. 42 (5): 971–983. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F210118.210128">10.1145/210118.210128</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5813837">5813837</a>.</li></ul>
<ul><li>Manasse, Mark; McGeoch, Lyle A.; <a href="/facts/Daniel_Sleator/hLBuUyER">Sleator, Daniel D.</a> (1990). "Competitive algorithms for server problems". Journal of Algorithms. 11 (2): 208–230. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0196-6774%2890%2990003-W">10.1016/0196-6774(90)90003-W</a>.</li></ul>
<ul><li><a href="/facts/Daniel_Sleator/hLBuUyER">Sleator, Daniel D.</a>; <a href="/facts/Robert_Tarjan/kn1pMCN0">Tarjan, Robert E.</a> (1985). <a href="https://doi.org/10.1145%2F2786.2793">"Amortized efficiency of list update and paging rules"</a>. Communications of the ACM. 28 (2): 202–208. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2786.2793">10.1145/2786.2793</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2494305">2494305</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Manasse, Mark; McGeoch, Lyle; Sleator, Daniel (1988-01-01). "Competitive algorithms for on-line problems". Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88. New York, NY, USA: Association for Computing Machinery. pp. 322–333. doi:10.1145/62212.62243. ISBN 978-0-89791-264-8. S2CID 13356897. <a href="978-0-89791-264-8" target="_blank">978-0-89791-264-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bubeck, Sébastien; Coester, Christian; Rabani, Yuval (June 20–23, 2023). The Randomized 𝑘-Server Conjecture Is False!. 55th Annual ACM Symposium on Theory of Computing (STOC '23). Orlando, FL, USA: ACM. p. 14. arXiv:2211.05753. doi:10.1145/3564246.3585132.{{cite conference}}: CS1 maint: date and year (link) <a href="https://doi.org/10.1145/3564246.3585132" target="_blank">https://doi.org/10.1145/3564246.3585132</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Bansal, Nikhil; Buchbinder, Niv; Madry, Aleksander; Naor, Joseph (2015). "A polylogarithmic-competitive algorithm for the k-server problem" (PDF). Journal of the ACM. 62 (5): A40:1–A40:49. arXiv:1110.1580. doi:10.1145/2783434. MR 3424197. S2CID 15668961. <a href="/wiki/Joseph_Seffi_Naor" target="_blank">/wiki/Joseph_Seffi_Naor</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"Another Annoying Open Problem". 19 November 2011. <a href="http://rjlipton.wordpress.com/2011/11/19/another-annoying-open-problem/" target="_blank">http://rjlipton.wordpress.com/2011/11/19/another-annoying-open-problem/</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Lee, James R. (2017). "Fusible HSTs and the Randomized k-Server Conjecture". arXiv:1711.01789 [cs.DS]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Erratum: Fusible HSTS and the randomized k-server conjecture". <a href="https://homes.cs.washington.edu/~jrl/papers/kserver-erratum.html" target="_blank">https://homes.cs.washington.edu/~jrl/papers/kserver-erratum.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Bubeck, Sébastien; Coester, Christian; Rabani, Yuval (June 20–23, 2023). The Randomized 𝑘-Server Conjecture Is False!. 55th Annual ACM Symposium on Theory of Computing (STOC '23). Orlando, FL, USA: ACM. p. 14. arXiv:2211.05753. doi:10.1145/3564246.3585132.{{cite conference}}: CS1 maint: date and year (link) <a href="https://doi.org/10.1145/3564246.3585132" target="_blank">https://doi.org/10.1145/3564246.3585132</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Goldberg, Madison (2023-11-20). "Researchers Refute a Widespread Belief About Online Algorithms". Quanta Magazine. Retrieved 2023-11-26. <a href="https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/" target="_blank">https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">The video presentation of the paper "The Randomized k-Server Conjecture is False!" at STOC 2023 is available in YouTube. <a href="https://www.youtube.com/watch?v=uIM08IuDwuQ" target="_blank">https://www.youtube.com/watch?v=uIM08IuDwuQ</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

k-server problem open-in-new

k-server problem