Online packet scheduling with bounded delay and lookahead
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404878" target="_blank" >RIV/00216208:11320/19:10404878 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=A.kn0WUlc5" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=A.kn0WUlc5</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2019.01.013" target="_blank" >10.1016/j.tcs.2019.01.013</a>
Alternative languages
Result language
angličtina
Original language name
Online packet scheduling with bounded delay and lookahead
Original language description
We study the online bounded delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature; yet currently the best published upper bound is 1.828 [8], still quite far from the best lower bound of phi approximate to 1.618 [11,2,6]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a phi-competitive algorithm for 4 bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1- lookahead, knowing at time t which packets will arrive at time t + 1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio 1/2 (root 13-1) approximate to 1.303 and we prove a nearly tight lower bound of 1/4 (1 + root 17) approximate to 1.281. In fact, our lower bound result is more general: using only 2-bounded instances, for any integer l >= 0 we prove a lower bound of 1/2(l+1) (1+root 5+8l+4l(2)) for online algorithms with l-lookahead, i.e., algorithms that at time t can see all packets arriving by time t + l. Finally, for non-restricted instances we show a lower bound of 1.25 for randomized algorithms with l-lookahead, for any l >= 0.
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
2019
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
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Volume of the periodical
776
Issue of the periodical within the volume
July 2019
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
19
Pages from-to
95-113
UT code for WoS article
000470948700006
EID of the result in the Scopus database
2-s2.0-85060101147