| Publikationstyp: | Konferenz: Paper |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | Disjoint path allocation with sublinear advice |
| Autor/-in: | Gebauer, Heidi Komm, Dennis Královič, Rastislav Královič, Richard Smula, Jasmin |
| DOI: | 10.1007/978-3-319-21398-9_33 |
| Tagungsband: | Computing and Combinatorics |
| Seite(n): | 417 |
| Seiten bis: | 429 |
| Angaben zur Konferenz: | 21st International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 4-6 August 2015 |
| Erscheinungsdatum: | 2015 |
| Reihe: | Lecture Notes in Computer Science |
| Reihenzählung: | 9198 |
| Verlag / Hrsg. Institution: | Springer |
| Verlag / Hrsg. Institution: | Cham |
| ISBN: | 978-3-319-21397-2 978-3-319-21398-9 |
| ISSN: | 0302-9743 1611-3349 |
| Sprache: | Englisch |
| Schlagwörter: | Competitive ratio; Input length; Online algorithm; Hypergeometric distribution; Deterministic algorithm |
| Fachgebiet (DDC): | 500: Naturwissenschaften |
| Zusammenfassung: | 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. |
| URI: | https://digitalcollection.zhaw.ch/handle/11475/15845 |
| Volltext Version: | Publizierte Version |
| Lizenz (gemäss Verlagsvertrag): | Lizenz gemäss Verlagsvertrag |
| Departement: | School of Engineering |
| Organisationseinheit: | Institut für Angewandte Mathematik und Physik (IAMP) |
| Enthalten in den Sammlungen: | Publikationen School of Engineering |
Dateien zu dieser Ressource:
Es gibt keine Dateien zu dieser Ressource.
Zur Langanzeige
Gebauer, H., Komm, D., Královič, R., Královič, R., & Smula, J. (2015). Disjoint path allocation with sublinear advice [Conference paper]. Computing and Combinatorics, 417–429. https://doi.org/10.1007/978-3-319-21398-9_33
Gebauer, H. et al. (2015) ‘Disjoint path allocation with sublinear advice’, in Computing and Combinatorics. Cham: Springer, pp. 417–429. Available at: https://doi.org/10.1007/978-3-319-21398-9_33.
H. Gebauer, D. Komm, R. Královič, R. Královič, and J. Smula, “Disjoint path allocation with sublinear advice,” in Computing and Combinatorics, 2015, pp. 417–429. doi: 10.1007/978-3-319-21398-9_33.
GEBAUER, Heidi, Dennis KOMM, Rastislav KRÁLOVIČ, Richard KRÁLOVIČ und Jasmin SMULA, 2015. Disjoint path allocation with sublinear advice. In: Computing and Combinatorics. Conference paper. Cham: Springer. 2015. S. 417–429. ISBN 978-3-319-21397-2
Gebauer, Heidi, Dennis Komm, Rastislav Královič, Richard Královič, and Jasmin Smula. 2015. “Disjoint Path Allocation with Sublinear Advice.” Conference paper. In Computing and Combinatorics, 417–29. Cham: Springer. https://doi.org/10.1007/978-3-319-21398-9_33.
Gebauer, Heidi, et al. “Disjoint Path Allocation with Sublinear Advice.” Computing and Combinatorics, Springer, 2015, pp. 417–29, https://doi.org/10.1007/978-3-319-21398-9_33.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.