AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

Antonios Antoniadis

--email hidden

passcode not visible

logged in users only