1. ZHAW digitalcollection
  2. School of Engineering
  3. Publikationen
  4. Publikationen School of Engineering
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGebauer, Heidi-
dc.contributor.authorKomm, Dennis-
dc.contributor.authorKrálovič, Rastislav-
dc.contributor.authorKrálovič, Richard-
dc.contributor.authorSmula, Jasmin-
dc.date.accessioned2019-03-06T15:45:31Z-
dc.date.available2019-03-06T15:45:31Z-
dc.date.issued2015-
dc.identifier.isbn978-3-319-21397-2de_CH
dc.identifier.isbn978-3-319-21398-9de_CH
dc.identifier.issn0302-9743de_CH
dc.identifier.issn1611-3349de_CH
dc.identifier.urihttps://digitalcollection.zhaw.ch/handle/11475/15845-
dc.description.abstractWe 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.de_CH
dc.language.isoende_CH
dc.publisherSpringerde_CH
dc.relation.ispartofseriesLecture Notes in Computer Sciencede_CH
dc.rightsLicence according to publishing contractde_CH
dc.subjectCompetitive ratiode_CH
dc.subjectInput lengthde_CH
dc.subjectOnline algorithmde_CH
dc.subjectHypergeometric distributionde_CH
dc.subjectDeterministic algorithmde_CH
dc.subject.ddc500: Naturwissenschaftende_CH
dc.titleDisjoint path allocation with sublinear advicede_CH
dc.typeKonferenz: Paperde_CH
dcterms.typeTextde_CH
zhaw.departementSchool of Engineeringde_CH
zhaw.organisationalunitInstitut für Angewandte Mathematik und Physik (IAMP)de_CH
zhaw.publisher.placeChamde_CH
dc.identifier.doi10.1007/978-3-319-21398-9_33de_CH
zhaw.conference.details21st International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 4-6 August 2015de_CH
zhaw.funding.euNode_CH
zhaw.originated.zhawYesde_CH
zhaw.pages.end429de_CH
zhaw.pages.start417de_CH
zhaw.publication.statuspublishedVersionde_CH
zhaw.series.number9198de_CH
zhaw.publication.reviewPeer review (Publikation)de_CH
zhaw.title.proceedingsComputing and Combinatoricsde_CH
Appears in collections:Publikationen School of Engineering

Files in This Item:
There are no files associated with this item.
Show simple item record
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.


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