The on-line asymmetric traveling salesman problem

DOI10.1016/j.jda.2007.03.002zbMath1163.90400OpenAlexW2129260095MaRDI QIDQ935844

Luigi Laura, Vincenzo Bonifaci, Giorgio Ausiello

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.03.002

zbMATH Keywords

competitive analysison-line algorithmsasymmetric traveling salesman problemreal time vehicle routing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Related Items (6)

Optimal deterministic algorithms for some variants of online quota traveling salesman problem ⋮ A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Online TSP with known locations ⋮ On the power of lookahead in on-line server routing problems ⋮ Discrete online TSP

Cites Work

• Algorithms for the on-line quota traveling salesman problem
• Online algorithms. The state of the art
• The traveling salesman problem and its variations
• The Online TSP Against Fair Adversaries
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• P-Complete Approximation Problems
• The Traveling Salesman Problem with Distances One and Two
• 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: The on-line asymmetric traveling salesman problem