K- servern problemet är ett grundläggande online problem där k mobila servrar bör schemaläggas för att svara på en sekvens av förfrågningar om punkter i ett metriska utrymme för att minimera den totala rörelsekostnaden. Medan det deterministiska konkurrensförhållandet är minst k, har randomiserade k-serveralgoritmer potential att nå o(k) konkurrensförhållanden. Detta mål kan nås genom att använda probabilistiska metrisk approximeringsmetoder. Detta papper ger de första resultaten i denna riktning erhålla o(k) konkurrensförhållande för en naturlig klass av metriska utrymmen, inklusive d-dimensionella rutnät, och brett spektrum av k. Före detta arbete inga resultat av denna typ var kända bortom resultat för specifika metriska utrymmen. K-serverproblemet, definierat av Manasse, McGeoch och Sleator [18], består av ett n-punktsmätutrymme och k-mobilservrar (k < n) som befinner sig i punkter i detta metriska utrymme. En sekvens av förfrågningar presenteras, varje begäran är associerad med en punkt i det metriska utrymmet och måste serveras genom att flytta en av k-servrarna till begäran punkt. Kostnaden för en algoritm för att uppfylla en sekvens av förfrågningar är det totala avstånd som transporteras av servrarna. Problemet är formulerat som ett online-problem, där servrarna algoritm måste fatta beslutet rörelse utan kunskap om framtida förfrågningar. Anteckna med kostnad A (σ) kostnaden för en algoritm A för att uppfylla begäran σ (om A är randomiserad algoritm, detta är en slumpmässig variabel), och genom kostnad opt (σ) den minimala kostnaden för att tjäna σ. Som brukligt för online-algoritmer mäter vi deras prestanda med hjälp av konkurrensförhållandet. En randomiserad onlinealgoritm A kallas r-konkurrenskraft om det finns någon C sådan att för någon uppgift sekvens σ, [kostnad A (σ)] ≤ r kostnad opt (σ) + C. Den randomiserade (resp. Deterministiskt) konkurrensförhållande är det infimum över r för vilket det finns en randomiserad (resp. Deterministisk) r-konkurrensalgoritm. K-server problemet lockade mycket forskning,
En av de väl studerade online algoritmen för att tilldela resurser till användare är Kserver problem REF där servrarna hanterar begäran en gång för varje klient.
Randomized k-server algorithms for growth-rate bounded graphs
{'venue': "SODA '04", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}