Reoptimization of minimum and maximum traveling salesman's tours

DOI10.1016/j.jda.2008.12.001zbMath1180.90259OpenAlexW2043636453MaRDI QIDQ1044031

Giorgio Ausiello, Jérôme Monnot, Vangelis Th. Paschos, Bruno Escoffier

Publication date: 10 December 2009

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

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

zbMATH Keywords

traveling salesman problemapproximation algorithmsreoptimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

A survey on combinatorial optimization in dynamic environments ⋮ Robust reoptimization of Steiner trees ⋮ Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications ⋮ Unnamed Item ⋮ Fixing improper colorings of graphs ⋮ Analysis and Experimental Study of Heuristics for Job Scheduling Reoptimization Problems ⋮ A theory and algorithms for combinatorial reoptimization ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ Reallocation problems in scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved deterministic approximation algorithms for max TSP
• The traveling salesman problem and its variations
• A \(\frac78\)-approximation algorithm for metric Max TSP
• Reoptimization of Steiner Trees
• P-Complete Approximation Problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Sparsification—a technique for speeding up dynamic graph algorithms
• Reoptimizing the traveling salesman problem
• Maintaining minimum spanning trees in dynamic graphs
• The Traveling Salesman Problem with Distances One and Two
• Scheduling with forbidden sets