Multiple canadians on the road: minimizing the distance competitive ratio

DOI10.1007/s10878-019-00438-6zbMath1432.90130OpenAlexW2961784693WikidataQ127464688 ScholiaQ127464688MaRDI QIDQ2279750

Wen Guo, Arpad Rimmel, Pierre Bergé, Joanna Tomasik, Aurélie Lefebvre, Jean Desmarchelier

Publication date: 13 December 2019

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

Full work available at URL: https://doi.org/10.1007/s10878-019-00438-6

zbMATH Keywords

communicationcompetitive analysisCanadian traveller problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (1)

The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest paths without a map
• A note on the \(k\)-Canadian traveller problem
• An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths
• The \(k\)-Canadian travelers problem with communication
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• Canadians Should Travel Randomly

This page was built for publication: Multiple canadians on the road: minimizing the distance competitive ratio