A $\Phi$-Competitive Algorithm for Collecting Items with Increasing Weights from a Dynamic Queue
Résumé
The bounded-delay packet scheduling (or buffer management) problem is to schedule transmissions of packets arriving in a buffer of a network link. Each packet has a deadline and a weight associated with it. The objective is to maximize the weight of packets that are transmitted before their deadlines, assuming that only one packet can be transmitted in one time step. Online packet scheduling algorithms have been extensively studied. It is known that no online algorithm can achieve a competitive ratio better than $\Phi \approx 1.618$ (the golden ratio), while the currently best upper bound on the competitive ratio is $2 \sqrt 2 - 1 \approx 1.824$. Closing the gap between these bounds remains a major open problem.
The above mentioned lower bound of $\Phi$ uses instances where item weights increase exponentially over time. In fact, all lower bounds for various versions of buffer management problems involve instances of this type. In this paper, we design an online algorithm for packet scheduling with competitive ratio $\Phi$ when packet weights are increasing, thus matching this lower bound. Our algorithm applies, in fact, to a much more general version of packet scheduling, where only the relative order of the deadlines is known, not their exact values.