I den här artikeln studerar vi en stokastisk variant av det berömda K-server-problemet. I kserver- problemet är vi skyldiga att minimera den totala förflyttningen av k- servrar som betjänar en online sekvens av t- förfrågningar i ett metriska. I den stokastiska inställningen får vi t oberoende distributioner P 1, P 2,. .., P t i förväg, och varje gång steg i en begäran hämtas från P i. Att utforma den optimala online-algoritmen i en sådan miljö är NP-hård, därför ligger tyngdpunkten i vårt arbete på att utforma en ungefär optimal online-algoritm. Vi visar först en strukturell karakterisering för en viss klass av icke-adaptiva online-algoritmer. Vi bevisar att i allmänna mått, den bästa av sådana algoritmer har en kostnad av inte sämre än tre gånger den optimala online algoritm. Därefter presenterar vi ett heltal program som finner den optimala algoritmen för denna klass för alla godtyckliga metriska. Slutligen genom avrundning lösningen av linjär avslappning av detta program, presenterar vi en online-algoritm för den stokastiska k-server problem med en approximationsfaktor på 3 i linjen och cirkelmått och faktor O(log n) i en allmän metrisk storlek n. På detta sätt uppnår vi en approximationsfaktor som är oberoende av k, antalet servrar. Dessutom definierar vi Uber-problemet, som motiveras av en extraordinär tillväxt av nättransporttjänster. I Uber problemet, varje efterfrågan består av två punkter - en källa och en destination-i metriska. Att tjäna ett krav är att flytta en server till dess källa och sedan till dess destination. Målet är återigen att minimera den totala rörelsen för k givna servrar. Vi visar att med en α-tillnärmningsalgoritm för k-server-problemet kan vi få en (α + 2)-tillnärmningsalgoritm för Uber-problemet. Motiverad av det faktum att krav oftast är starkt korrelerade med tiden (t.ex. vilken dag i veckan eller vilken tid på dagen efterfrågan har kommit), studerar vi det stokastiska Uber problemet. Med hjälp av våra resultat för stokastisk k-server kan vi få en 5 approximation algoritm för stokastiska Uber problem i linje- och cirkelmått, och en O (log n)-uppskattning algoritm för allmänna mätvärden. Dessutom utvidgar vi våra resultat till den korrelerade inställningen där sannolikheten för att en begäran kommer till en viss punkt beror inte bara på tidssteget utan också på de tidigare inkomna förfrågningarna.
I REF beaktas ett annat slags konkurrensförhållande: de ger en online-algoritm med en kostnad som inte är värre än O(log (n)) gånger kostnaden för den optimala online-algoritmen.
Stochastic k-Server: How Should Uber Work?
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}