The covering Canadian traveller problem

DOI10.1016/j.tcs.2014.02.026zbMath1359.90122OpenAlexW1985734068MaRDI QIDQ2440168

Chung-Shou Liao, Yamming Huang

Publication date: 27 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.02.026

zbMATH Keywords

competitive ratiotravelling salesman problemonline algorithmCanadian traveller problem

Mathematics Subject Classification ID

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

Related Items (12)

The Steiner traveling salesman problem with online edge blockages ⋮ The Steiner traveling salesman problem with online advanced edge blockages ⋮ 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 ⋮ From theory to practice: maximizing revenues for on-line dial-a-ride ⋮ Online covering salesman problem ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Shortest paths without a map
• The dynamic shortest path problem with anticipation
• A note on the \(k\)-Canadian traveller problem
• The Canadian Traveller Problem and its competitive analysis
• The traveling salesman problem and its variations
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A review of dynamic vehicle routing problems
• Dynamic journeying under uncertainty
• An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths
• Online linear optimization and adaptive routing
• Efficient algorithms for online decision problems
• A Dynamic Traveling Salesman Problem with Stochastic Arc Costs
• The k-Canadian Travelers Problem with Communication
• Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses
• Recent Developments in Dynamic Vehicle Routing Systems
• Online Vehicle Routing Problems: A Survey
• The Canadian Traveller Problem Revisited
• Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs
• A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem
• Algorithms for the on-line travelling salesman

This page was built for publication: The covering Canadian traveller problem