Title: Disjoint path allocation with sublinear advice
Authors : Gebauer, Heidi
Komm, Dennis
Královič, Rastislav
Královič, Richard
Smula, Jasmin
Proceedings: Computing and Combinatorics
Pages : 417
Pages to: 429
Conference details: COCOON 2015, 21st International Computing and Combinatorics Conference, Beijing, China, 4-6 August 2015
Publisher / Ed. Institution : Springer
Publisher / Ed. Institution: Cham
Issue Date: 2015
License (according to publishing contract) : Licence according to publishing contract
Series : Lecture Notes in Computer Science
Series volume: 9198
Type of review: Peer review (publication)
Language : English
Subjects : Competitive ratio; Input length; Online algorithm; Hypergeometric distribution; Deterministic algorithm
Subject (DDC) : 500: Natural sciences and mathematics
Abstract: We study the disjoint path allocation problem. In this setting, a path P of length L is given, and a sequence of subpaths of P arrives online, one in every time step. Each such path requests a permanent connection between its two end-vertices. An online algorithm can admit or reject such a request; in the former case, none of the involved edges can be part of any other connection. We investigate how much additional binary information (called “advice”) can help to obtain a good solution. It is known that, with roughly log2log2L advice bits, it can be guaranteed that a log2L-competitive solution is computed. In this paper, we prove the surprising result that, with L1−ε advice bits, it is not possible to obtain a solution with a competitive ratio better than (δlog2L)/2, where 0<δ<ε<1. This shows an interesting threshold behavior of the problem. A fairly good competitive ratio, namely log2L, can be obtained with very few advice bits. However, any increase of the advice does not help any further until an almost linear number of advice bits is supplied. Then again, it is also known that linear advice allows for optimality.
Departement: School of Engineering
Organisational Unit: Institute of Applied Mathematics and Physics (IAMP)
Publication type: Conference paper
DOI : 10.1007/978-3-319-21398-9_33
ISBN: 978-3-319-21397-2
ISSN: 0302-9743
URI: https://digitalcollection.zhaw.ch/handle/11475/15845
Appears in Collections:Publikationen School of Engineering

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.