A phi-Competiitve Algorithm for Scheduling Packets with Deadlines

Speaker:        Professor Marek Chrobak
                University of California at Riverside

Title:          "A phi-Competiitve Algorithm for Scheduling Packets
                 with Deadlines"

Date:           Monday, 3 December 2018

Time:           11 AM - 12 Noon

Venue:          Room 4472 (near lift 25/26), HKUST

Abstract:

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 central problem concerning packet scheduling, that has been a subject
of intensive study since 2001, is to determine the optimal competitive
ratio of online algorithms, namely 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.
We solve this open problem by presenting a f-competitive online algorithm
(where ϕ ≈ 1.618 is the golden ratio), matching the previously
established lower bound.


*****************
Biography:

Marek Chrobak is currently a Professor of Computer Science at University
of California, Riverside. Born in Poland, he received his PhD from Warsaw
University in 1985, and soon afterwards moved to UCR and stayed there ever
since, enticed by its sunny weather, proximity to nature, and friendly
atmosphere. In his research, he is generally interested in theoretical
computer science, with his current research topics including offline and
online approximation algorithms, information dissemination in radio
networks, and job scheduling problems, although in the past he also tried
his luck in other areas, including automata theory and bioinformatics.