Algorithms for the on-line quota traveling salesman problem

DOI10.1016/j.ipl.2004.06.013zbMath1178.90282OpenAlexW1989571340MaRDI QIDQ834904

Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos

Publication date: 27 August 2009

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

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2525

zbMATH Keywords

traveling salesman problemon-line algorithmsquota TSP

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (18)

Optimal deterministic algorithms for some variants of online quota traveling salesman problem ⋮ Particle swarm optimization-based algorithms for TSP and generalized TSP ⋮ TSP race: minimizing completion time in time-sensitive applications ⋮ A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths ⋮ Orienteering problem with time-windows and updating delay ⋮ Tight analysis of the lazy algorithm for open online dial-a-ride ⋮ Online TSP with known locations ⋮ An improved algorithm for open online dial-a-ride ⋮ Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems ⋮ The on-line asymmetric traveling salesman problem ⋮ Online traveling salesman problem with deadlines and service flexibility ⋮ Online Vehicle Routing Problems: A Survey ⋮ Biogeography migration algorithm for traveling salesman problem ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ On the power of lookahead in on-line server routing problems ⋮ The online prize-collecting traveling salesman problem ⋮ Online traveling salesman problems with service flexibility ⋮ Prize-Collecting TSP with a Budget Constraint

Cites Work

• A 2.5-factor approximation algorithm for the \(k\)-MST problem
• Online algorithms. The state of the art
• The Online TSP Against Fair Adversaries
• The prize collecting traveling salesman problem
• Special cases of traveling salesman and repairman problems with time windows
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Algorithms for the on-line travelling salesman
• On-line single-server dial-a-ride problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithms for the on-line quota traveling salesman problem