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.

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
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2016020/

S. Albers, Online algorithms: a survey. Math. Program. 97 (2003) 3–26. | DOI | MR | Zbl

K. Barhum, H.-J. Böckenhauer, M. Forišek, H. Gebauer, J. Hromkovič, S. Krug, J. Smula and B. Steffen, On the power of advice and randomization for the disjoint path allocation problem. In Proc. of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014). Vol. 8327 of Lect. Notes Comput. Sci. Springer (2014) 89–101. | MR

H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič and T. Mömke, On the advice complexity of online problems. In Proc. of Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Edited by Y. Dong, D.-Z. Du and O.H. Ibarra. Vol. 5878 of Lect. Notes Comput. Sci. Springer (2009) 331–340. | Zbl

A. Borodin and R. El-Yaniv, Online computation and competitive analysis. Cambridge University Press (1998). | MR | Zbl

S. Dobrev, R. Královič and D. Pardubská, Measuring the problem-relevant information in input. RAIRO: ITA 43 (2009) 585–613. | Numdam | MR | Zbl

Y. Emek, P. Fraigniaud, A. Korman and A. Rosén, Online computation with advice. Special issue of ICALP’09. Theoret. Comput. Sci. 412 (2011) 2642–2656. | DOI | MR | Zbl

R.L. Graham, Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45 (1966) 1563–1581. | DOI | Zbl

D. Komm, Advice and randomization in online computation. Ph.D. thesis, ETH Zürich (2011).

T.III Piezas, F. van Lamoen and E.W. Weisstein, “Plastic Constant” From MathWorld – A Wolfram Web Resource. Available at http://mathworld.wolfram.com/PlasticConstant.html (2015).

D.D. Sleator and R.E. Tarjan, Amortized efficiency of list update and paging rules. Commun. ACM 28 (1985) 202–208. | DOI | MR

N.J.A. Sloane, “Padovan sequence(A000931)” From The On-Line Encyclopedia of Integer Sequences. Available at https://oeis.org/A000931 (2015).

A. Sprock, Analysis of hard problems in reoptimization and online computation. Ph.D. thesis, ETH Zürich (2013).

E.W. Weisstein, “Padovan Sequence” From MathWorld – A Wolfram Web Resource. Available at http://mathworld.wolfram.com/PadovanSequence.html (2015).

Cité par Sources :