De $k$-server conjectuur is waar

Samenvatting

De $k$-server conjectuur stelt dat een deterministisch online algoritme een competitieve ratio van $k$ kan behalen in elke metrische ruimte. Wij bewijzen deze conjectuur. Specifiek tonen we aan dat het work function algoritme hieraan voldoet.

Ons bewijs maakt gebruik van een natuurlijke algebraïsche representatie van de work function als een matrix, die alle haalbare paden codeert om een configuratie te bereiken. In deze representatie komen de minimum- en optellingsoperaties die voortvloeien uit de definitie van optimale kosten overeen met de optelling en vermenigvuldiging van formele expressies. Elke work function waarde komt hierbij overeen met de determinant van $k$ kolommen van de matrix.

Wanneer er een verzoek binnenkomt, wordt de representatie bijgewerkt via een basisverandering en rijvervanging. De geamortiseerde analyse is gebaseerd op een potentiaalfunctie die is gedefinieerd in termen van een grotere matrix, waarvan de coördinaten paren zijn van coördinaten uit de oorspronkelijke matrixrepresentatie.