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%2F18%3A10385248" target="_blank" >RIV/00216208:11320/18:10385248 - isvavai.cz</a>
Result on the web
<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>
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 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
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
2018
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
Article name in the collection
APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2017
ISBN
978-3-319-89440-9
ISSN
0302-9743
e-ISSN
neuvedeno
Number of pages
17
Pages from-to
190-206
Publisher name
SPRINGER-VERLAG BERLIN
Place of publication
BERLIN
Event location
Vienna
Event date
Sep 7, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—