  In the online packet scheduling problem with deadlines (PacketSchD, 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 that are successfully
transmitted. The problem is inherently online, with the scheduling decisions
made without the knowledge of future packet arrivals. The central problem
concerning PacketSchD, 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 $\phi$-competitive online
algorithm for PacketSchD (where $\phi\approx 1.618$ is the golden ratio),
matching the previously established lower bound.
