Die k-Server-Vermutung ist bewiesen

The k-server conjecture is true

Christian Coester, Elias Koutsoupias und Marek Zbysiński haben die k-Server-Vermutung bewiesen, die besagt, dass ein deterministischer Online-Algorithmus in jedem metrischen Raum ein kompetitives Verhältnis von k erreichen kann. Sie zeigen, dass der Work Function Algorithm diese Schranke erfüllt. Der Beweis nutzt eine algebraische Darstellung der Work Function als Matrix, in der sich die optimalen Kosten als Determinanten von k Spalten wiederfinden. Eine Anfrage aktualisiert die Darstellung durch Basiswechsel und Zeilenersetzung; die amortisierte Analyse basiert auf einer Potentialfunktion über eine größere Matrix.