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:A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines
Speaker:Pavel Vesely
coming from:University of Warwick
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 21 March 2019
Duration:30 Minutes
Building:E1 4
In the online packet scheduling problem with deadlines, the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The goal is to develop an algorithm with the lowest possible competitive ratio, which is the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm.

In this talk, we present a ϕ-competitive online algorithm (where ϕ≈1.618 is the golden ratio), matching the previously established lower bound. We then outline main ideas of its analysis and discuss possible extensions of this work.

Joint work with Marek Chrobak, Łukasz Jeż, and Jiří Sgall.

Name(s):Antonios Antoniadis
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Antonios Antoniadis, 02/21/2019 12:41 PM
Last modified:
Uwe Brahm/MPII/DE, 03/21/2019 04:01 AM
  • Antonios Antoniadis, 02/21/2019 12:41 PM -- Created document.