A note on the \(k\)-Canadian traveller problem

DOI10.1016/J.IPL.2007.10.004zbMath1186.68570OpenAlexW2092129437MaRDI QIDQ963338

Stephan Westphal

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.10.004

zbMATH Keywords

on-line algorithmsroutingcompetitiveness

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Online algorithms; streaming algorithms (68W27)

Related Items (26)

Robust optimization for routing problems on trees ⋮ Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ The Steiner traveling salesman problem with online edge blockages ⋮ The Canadian tour operator problem on paths: tight bounds and resource augmentation ⋮ The Steiner traveling salesman problem with online advanced edge blockages ⋮ The \(k\)-Canadian travelers problem with communication ⋮ 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 ⋮ Complexity of Canadian traveler problem variants ⋮ 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 ⋮ Online interval scheduling with a bounded number of failures ⋮ The covering Canadian traveller problem ⋮ The k-Canadian Travelers Problem with Communication ⋮ Online covering salesman problem ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ Multiple canadians on the road: minimizing the distance competitive ratio ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ The Canadian Traveller Problem and its competitive analysis ⋮ A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem ⋮ Generalized Canadian traveller problems ⋮ An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths

Cites Work

• Shortest paths without a map
• A new measure for the study of on-line algorithms
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on the \(k\)-Canadian traveller problem