An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths

DOI10.1007/s10878-013-9634-8zbMath1325.90094OpenAlexW2043815754WikidataQ57851363 ScholiaQ57851363MaRDI QIDQ2352354

Marco Bender, Stephan Westphal

Publication date: 1 July 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9634-8

zbMATH Keywords

competitive analysisonline algorithmCanadian traveller problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (13)

The Canadian tour operator problem on paths: tight bounds and resource augmentation ⋮ Online routing and searching on graphs with blocked edges ⋮ Approximating the Canadian traveller problem with online randomization ⋮ On the online multi-agent O-D \(k\)-Canadian traveler problem ⋮ An online optimization approach for post-disaster relief distribution with online blocked edges ⋮ The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem ⋮ Competitive analysis of randomized online strategies for the multi-agent \(k\)-Canadian traveler problem ⋮ On the randomized online strategies for the \(k\)-Canadian traveler problem ⋮ Canadian traveller problem with predictions ⋮ The covering Canadian traveller problem ⋮ Online failure diagnosis in interdependent networks ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ Multiple canadians on the road: minimizing the distance competitive ratio

Cites Work

• Shortest paths without a map
• A note on the \(k\)-Canadian traveller problem
• The Canadian Traveller Problem and its competitive analysis
• A new measure for the study of on-line algorithms
• A risk-reward framework for the competitive analysis of financial games
• The k-Canadian Travelers Problem with Communication
• The Canadian Traveller Problem Revisited
• A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem
• Unnamed Item
• Unnamed Item

This page was built for publication: An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths