Westphal, Stephan

[["dc.bibliographiccitation.firstpage","87"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","Journal of Combinatorial Optimization"],["dc.bibliographiccitation.lastpage","96"],["dc.bibliographiccitation.volume","30"],["dc.contributor.author","Bender, Marco"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T09:55:30Z"],["dc.date.available","2018-11-07T09:55:30Z"],["dc.date.issued","2015"],["dc.description.abstract","We consider the -Canadian Traveller Problem, which asks for a shortest path between two nodes and in an undirected graph, where up to edges may be blocked. An online algorithm learns about a blocked edge when reaching one of its endpoints. Recently, it has been shown that no randomized online algorithm can be better than -competitive, even if all --paths are node-disjoint. We show that the bound is tight by constructing a randomized online algorithm for this case that achieves the ratio against an oblivious adversary and is therefore best possible."],["dc.description.sponsorship","DFG RTG [1703]"],["dc.identifier.doi","10.1007/s10878-013-9634-8"],["dc.identifier.isi","000355630900007"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/36754"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Springer"],["dc.relation.issn","1573-2886"],["dc.relation.issn","1382-6905"],["dc.title","An optimal randomized online algorithm for the -Canadian Traveller Problem on node-disjoint paths"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]