RAIRO-Theor. Inf. Appl.
Volume 50, Number 2, April-June 2016
|Page(s)||171 - 191|
|Published online||10 November 2016|
Advice complexity of disjoint path allocation
Department of Computer Science, Comenius
University, Bratislava, Slovakia.
Accepted: 13 September 2016
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.
Mathematics Subject Classification: 68Q25 / 68R10 / 68W27
Key words: Advice complexity / online problems / disjoint path allocation
© EDP Sciences 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.