Improved deterministic strategy for the Canadian Traveller Problem exploiting small max-(s,t)-cuts

DOI10.1007/978-3-030-39479-0_3MaRDI QIDQ2193076zbMATH OpenOpenAlexFDO

Authors Pierre Bergé, Lou Salaün

Publication date 24 August 2020

Full work available at URL https://doi.org/10.1007/978-3-030-39479-0_3

zbMATH Keywords

Canadian Traveller Problemcompetitive analysisonline algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem
• An \(\mathrm{AO}^{*}\) based exact algorithm for the Canadian traveler problem
• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• On the randomized online strategies for the \(k\)-Canadian traveler problem
• On the competitiveness of memoryless strategies for the \(k\)-Canadian traveller problem
• The Canadian tour operator problem on paths: tight bounds and resource augmentation
• An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths
• Approximating the Canadian traveller problem with online randomization
• Competitive analysis of randomized online strategies for the multi-agent \(k\)-Canadian traveler problem
• Improved deterministic approximation algorithms for max TSP

Cited in

(3)

• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem

This page was built for publication: Improved deterministic strategy for the Canadian Traveller Problem exploiting small max-\((s,t)\)-cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2193076)