Vi introducerar en naturlig variant av (metrisk okapacitet) k-median problem som vi kallar online median problem. Problemet med k-median innebär att man optimerar samtidig placering av k-anläggningar, medianproblemet online medför följande ytterligare begränsningar: anläggningarna placeras en i taget. En anläggning kan inte flyttas när den väl har placerats, och det totala antalet anläggningar som ska placeras, k, är inte känt i förväg. Målet med en online-medianalgoritm är att minimera konkurrensförhållandet, det vill säga det värsta tänkbara förhållandet mellan kostnaden för en online-placering och kostnaden för en optimal offline-placering. Vårt huvudsakliga resultat är en linjär-tid konstant-konkurrenskraftig algoritm för online median problem. Dessutom presenterar vi en relaterad, men betydligt enklare, linjär tid konstant-faktor approximationsalgoritm för (metrisk okapacitet) anläggning lokaliseringsproblem. Den senare algoritmen liknar i andemeningen Jains och Vaziranis senaste primära och dubbla lokaliseringsalgoritm, men vårt tillvägagångssätt är mer elementärt och ger en förbättrad körtid.
Till exempel introducerade Mettu och Plaxton REF problemet online k-median där platser visas och måste tilldelas sekventiellt och värdet av k inte är känt i förväg, och så målet är att när k slutligen väljs, finns det en lösning som inte är långt från optimal offline placering av k platser.
The Online Median Problem
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}