The Canadian Traveller Problem and its competitive analysis

DOI10.1007/s10878-008-9156-yzbMath1173.90524OpenAlexW2078856178MaRDI QIDQ1037454

Zhijun Zhu, Binhai Zhu, Bing Su, Maolin Hu, Yin-Feng Xu

Publication date: 16 November 2009

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

Full work available at URL: https://doi.org/10.1007/s10878-008-9156-y

zbMATH Keywords

competitive analysisonline algorithmsgreedy strategycomparison strategy

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (22)

The Steiner traveling salesman problem with online edge blockages ⋮ 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 ⋮ Complexity of Canadian traveler problem variants ⋮ How much the grid network and rescuers' communication can improve the rescue efficiency in worst-case analysis ⋮ The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem ⋮ On the randomized online strategies for the \(k\)-Canadian traveler problem ⋮ Optimal obstacle placement with disambiguations ⋮ Penalty-Based Algorithms for the Stochastic Obstacle Scene Problem ⋮ Canadian traveller problem with predictions ⋮ The covering Canadian traveller problem ⋮ The k-Canadian Travelers Problem with Communication ⋮ An AO^* Based Exact Algorithm for the Canadian Traveler Problem ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem ⋮ Optimal shortest path set problem in undirected graphs ⋮ Generalized Canadian traveller problems ⋮ An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths ⋮ Walking in streets with minimal sensing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shortest paths without a map
• A note on the \(k\)-Canadian traveller problem
• Online algorithms. The state of the art
• Competitive \(k\)-server algorithms
• Efficient algorithms for online decision problems
• 10.1162/1532443041424328
• Routing without regret

This page was built for publication: The Canadian Traveller Problem and its competitive analysis