Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Weighted k-Server Bounds via Combinatorial Dichotomies
Speaker:Grigorios Koumoutsos
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 6 March 2018
Duration:30 Minutes
Building:E1 4

The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap.

The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.

Joint work with Nikhil Bansal and Marek Elias, appeared in FOCS 2017.

Name(s):Yun Kuen Cheung
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Yun Kuen Cheung, 03/02/2018 03:13 PM
Last modified:
Uwe Brahm/MPII/DE, 03/06/2018 07:01 AM
  • Yun Kuen Cheung, 03/02/2018 03:13 PM -- Created document.