A phi-COMPETITIVE ALGORITHM FOR SCHEDULING PACKETS WITH DEADLINES
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455543" target="_blank" >RIV/00216208:11320/22:10455543 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=WQsK0c3KUK" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=WQsK0c3KUK</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/21M1469753" target="_blank" >10.1137/21M1469753</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A phi-COMPETITIVE ALGORITHM FOR SCHEDULING PACKETS WITH DEADLINES
Popis výsledku v původním jazyce
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 nonnegative weight, which 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 approximate to 1.618 is the golden ratio), matching the previously established lower bound.
Název v anglickém jazyce
A phi-COMPETITIVE ALGORITHM FOR SCHEDULING PACKETS WITH DEADLINES
Popis výsledku anglicky
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 nonnegative weight, which 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 approximate to 1.618 is the golden ratio), matching the previously established lower bound.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2022
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ů
Údaje specifické pro druh výsledku
Název periodika
SIAM Journal on Computing
ISSN
0097-5397
e-ISSN
1095-7111
Svazek periodika
51
Číslo periodika v rámci svazku
5
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
66
Strana od-do
1626-1691
Kód UT WoS článku
000883719100006
EID výsledku v databázi Scopus
2-s2.0-85142063199