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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00395509" target="_blank" >RIV/67985840:_____/13:00395509 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.tcs.2012.12.046" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2012.12.046</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2012.12.046" target="_blank" >10.1016/j.tcs.2012.12.046</a>

Result language
angličtina
Original language name
A phi-competitive algorithm for collecting items with increasing weights from a dynamic queue
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)