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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

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

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

475

Číslo periodika v rámci svazku

4 March

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

11

Strana od-do

92-102

Kód UT WoS článku

000315309600010

EID výsledku v databázi Scopus

—