Geodesic
Advice complexity of disjoint path allocation
Kováčová, Ivana1
1 Department of Computer Science, Comenius University, Bratislava, Slovakia.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 2, pp. 171-191

Voir la notice de l'article provenant de la source Numdam

This paper contributes to the research of advice complexity of online problems. Namely, we discuss the disjoint path allocation problem in various versions, based on the choice of values of the calls, and ability to preempt. The advice complexity is measured relative to either the length of the input sequence of requests, or the length of the input path. We provide lower and upper bounds on advice complexity of optimal online algorithms for these problems, and some bounds on trade-off between competitiveness and advice complexity. One of the results is an improved lower bound of n-1 on advice complexity for the non-preemptive version with constant values of calls. For all considered variations, the newly provided lower and upper bounds on advice complexity of optimal algorithms are linear, and therefore asymptotically tight.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016020
Classification : 68Q25, 68R10, 68W27
Keywords: Advice complexity, online problems, disjoint path allocation

Kováčová, Ivana 1

1 Department of Computer Science, Comenius University, Bratislava, Slovakia. 
@article{ITA_2016__50_2_171_0,
     author = {Kov\'a\v{c}ov\'a, Ivana},
     title = {Advice complexity of disjoint path allocation},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {171--191},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {2},
     year = {2016},
     doi = {10.1051/ita/2016020},
     mrnumber = {3580110},
     zbl = {1401.68122},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2016020/}
}
TY  - JOUR
AU  - Kováčová, Ivana
TI  - Advice complexity of disjoint path allocation
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 171
EP  - 191
VL  - 50
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2016020/
DO  - 10.1051/ita/2016020
LA  - en
ID  - ITA_2016__50_2_171_0
ER  - 
%0 Journal Article
%A Kováčová, Ivana
%T Advice complexity of disjoint path allocation
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 171-191
%V 50
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2016020/
%R 10.1051/ita/2016020
%G en
%F ITA_2016__50_2_171_0
Kováčová, Ivana. Advice complexity of disjoint path allocation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 2, pp. 171-191. doi: 10.1051/ita/2016020

Cité par Sources :