On Packet Scheduling with Adversarial Jamming and Speedup

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385248" target="_blank" >RIV/00216208:11320/18:10385248 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-319-89441-6_15" target="_blank" >https://doi.org/10.1007/978-3-319-89441-6_15</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-89441-6_15" target="_blank" >10.1007/978-3-319-89441-6_15</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Packet Scheduling with Adversarial Jamming and Speedup

Popis výsledku v původním jazyce

In Packet Scheduling with Adversarial Jamming packets of arbitrary sizes arrive over time to be transmitted over a channel in which instantaneous jamming errors occur at times chosen by the adversary and not known to the algorithm. The transmission taking place at the time of jamming is corrupt, and the algorithm learns this fact immediately. An online algorithm maximizes the total size of packets it successfully transmits and the goal is to develop an algorithm with the lowest possible asymptotic competitive ratio, where the additive constant may depend on packet sizes. Our main contribution is a universal algorithm that works for any speedup and packet sizes and, unlike previous algorithms for the problem, it does not need to know these properties in advance. We show that this algorithm guarantees 1-competitiveness with speedup 4, making it the first known algorithm to maintain 1-competitiveness with a moderate speedup in the general setting of arbitrary packet sizes.

Název v anglickém jazyce

On Packet Scheduling with Adversarial Jamming and Speedup

Popis výsledku anglicky

In Packet Scheduling with Adversarial Jamming packets of arbitrary sizes arrive over time to be transmitted over a channel in which instantaneous jamming errors occur at times chosen by the adversary and not known to the algorithm. The transmission taking place at the time of jamming is corrupt, and the algorithm learns this fact immediately. An online algorithm maximizes the total size of packets it successfully transmits and the goal is to develop an algorithm with the lowest possible asymptotic competitive ratio, where the additive constant may depend on packet sizes. Our main contribution is a universal algorithm that works for any speedup and packet sizes and, unlike previous algorithms for the problem, it does not need to know these properties in advance. We show that this algorithm guarantees 1-competitiveness with speedup 4, making it the first known algorithm to maintain 1-competitiveness with a moderate speedup in the general setting of arbitrary packet sizes.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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 statě ve sborníku

APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2017

ISBN

978-3-319-89440-9

ISSN

0302-9743

e-ISSN

neuvedeno

Počet stran výsledku

17

Strana od-do

190-206

Název nakladatele

SPRINGER-VERLAG BERLIN

Místo vydání

BERLIN

Místo konání akce

Vienna

Datum konání akce

7. 9. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—