15 lutego 2019 15:15
[Seminarium ZOK] Łukasz Jeż: "A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines" (SODA'19)
Tytuł: A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines
Autorzy: Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jirí Sgall:
Prelegent: Łukasz Jeż
Czas i miejsce: piątek, 15-go lutego 2019, 15:15 pm, sala 119.
Prezentacja ze slajdami, dość lekkowstawna, w zamierzeniu godzinna.
Streszczenie:
In the online packet scheduling problem with deadlines (PacketScheduling, for short), 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 PacketScheduling, 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 φ-competitive online algorithm for PacketSchedul-
ing (where φ ≈ 1.618 is the golden ratio), matching the previously established lower bound.