A phi-competitive algorithm for collecting items with increasing weights from a dynamic queue

作者：Bienkowski Marcin; Chrobak Marek; Duerr Christoph; Hurand Mathilde; Jez Artur; Jez Lukasz^*; Stachowiak Grzegorz

来源：Theoretical Computer Science, 2013, 475: 92-102.

DOI：10.1016/j.tcs.2012.12.046

• Online algorithms
• Competitive analysis
• Buffer management
• Packet scheduling

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 approximate to 1.618 (the golden ratio), while the currently best upper bound on the competitive ratio is 2 root 2 - 1 approximate to 1.824. Closing the gap between these bounds remains a major open problem. %26lt;br%26gt;The above mentioned lower bound of phi, uses instances where item weights increase exponentially overtime. 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.

• 出版日期2013-3-4