On inverse traveling salesman problems

DOI10.1007/s10288-011-0194-4zbMath1261.90041OpenAlexW2154020126MaRDI QIDQ1936660

Yerim Chung, Marc Demange

Publication date: 6 February 2013

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-011-0194-4

zbMATH Keywords

computational complexityinverse problemtraveling salesman problemsapproximation ratio2-opt heuristic

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (4)

The inverse connected \(p\)-median problem on block graphs under various cost functions ⋮ The 0–1 inverse maximum independent set problem on forests and unicyclic graphs ⋮ Inverse chromatic number problems in interval and permutation graphs ⋮ Notes on inverse bin-packing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• On the hardness of approximating minimum vertex cover
• Inverse minimum flow problem
• A tutorial on the use of graph coloring for some problems in robotics
• The 0-1 inverse maximum stable set problem
• Algorithms in order restricted statistical inference and the Cauchy mean value property
• On an instance of the inverse shortest paths problem
• On the use of an inverse shortest paths algorithm for recovering linearly correlated costs
• A general model of some inverse combinatorial optimization problems and its solution method under \(\ell_\infty\) norm
• The complexity analysis of the inverse center location problem
• Inverse combinatorial optimization: a survey on problems, methods, and results
• An inverse problem of the weighted shortest path problem
• Weighted isotonic regression under the L₁ norm
• Inverse Optimization
• Isotonic Median Regression: A Linear Programming Approach
• On Syntactic versus Computational Views of Approximability
• A Faster Algorithm for the Inverse Spanning Tree Problem
• Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
• Automata, Languages and Programming

This page was built for publication: On inverse traveling salesman problems