On packet scheduling with adversarial jamming and speedup
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10431448" target="_blank" >RIV/00216208:11320/21:10431448 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=0FxfoQWzBf" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=0FxfoQWzBf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10479-019-03153-x" target="_blank" >10.1007/s10479-019-03153-x</a>
Alternative languages
Result language
angličtina
Original language name
On packet scheduling with adversarial jamming and speedup
Original language description
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 parameters 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. We also prove a lower bound of phi+1 approximate to 2.618on the speedup of any 1-competitive deterministic algorithm, showing that our algorithm is close to the optimum. Additionally, we formulate a general framework for analyzing our algorithm locally and use it to show upper bounds on its competitive ratio for speedups in [1, 4) and for several special cases, recovering some previously known results, each of which had a dedicated proof. In particular, our algorithm is 3-competitive without speedup, matching both the (worst-case) performance of the algorithm by Jurdzinski et al. (Proceedings of the 12th workshop on approximation and online algorithms (WAOA), LNCS 8952, pp 193-206, 2015. ) and the lower bound by Anta et al. (J Sched 19(2):135-152, 2016. ).
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-09142S" target="_blank" >GA17-09142S: Modern algorithms: New challenges of complex data sets</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Annals of Operations Research
ISSN
0254-5330
e-ISSN
—
Volume of the periodical
298
Issue of the periodical within the volume
1-2
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
36
Pages from-to
7-42
UT code for WoS article
000617553900002
EID of the result in the Scopus database
2-s2.0-85061199732