Reoptimization of Minimum and Maximum Traveling Salesman’s Tours

DOI10.1007/11785293_20zbMath1141.90506OpenAlexW1505314250MaRDI QIDQ5757891

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

Publication date: 7 September 2007

Published in: Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (27)

Reoptimization of Steiner trees: changing the terminal set ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Reoptimization of parameterized problems ⋮ Reoptimization of constraint satisfaction problems with approximation resistant predicates ⋮ Reoptimizing the 0-1 knapsack problem ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ Reoptimization of NP-Hard Problems ⋮ Reoptimization of the shortest common superstring problem ⋮ On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems ⋮ Reoptimization of max \(k\)-cover: approximation ratio threshold ⋮ On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field ⋮ Reoptimization in machine scheduling ⋮ Knowing All Optimal Solutions Does Not Help for TSP Reoptimization ⋮ Reoptimization of set covering problems ⋮ Reoptimization of the metric deadline TSP ⋮ Reoptimization of the Metric Deadline TSP ⋮ Fast reoptimization for the minimum spanning tree problem ⋮ Reoptimization of Weighted Graph and Covering Problems ⋮ On the Hardness of Reoptimization ⋮ Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights ⋮ Structural Properties of Hard Metric TSP Inputs ⋮ Approximation hardness of deadline-TSP reoptimization ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ Finding Optimal Solutions With Neighborly Help. ⋮ New Reoptimization Techniques applied to Steiner Tree Problem

This page was built for publication: Reoptimization of Minimum and Maximum Traveling Salesman’s Tours