A note on the traveling salesman reoptimization problem under vertex insertion

DOI10.1016/J.IPL.2014.11.003MaRDI QIDQ483055zbMATH OpenOpenAlexFDO

Authors Jérôme Monnot

Publication date 15 December 2014

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

Full work available at URL https://doi.org/10.1016/j.ipl.2014.11.003

zbMATH Keywords

TSPapproximation algorithmsreoptimization under vertex insertion

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of minimum and maximum traveling salesman's tours
• Reoptimizing the traveling salesman problem
• Reoptimization of the Metric Deadline TSP
• Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights

Cites work

• scientific article; zbMATH DE number 5859273 (Why is no real title available?)
• scientific article; zbMATH DE number 5604770 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• A survey on combinatorial optimization in dynamic environments
• A theory and algorithms for combinatorial reoptimization
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Approximation hardness of deadline-TSP reoptimization
• Fast reoptimization for the minimum spanning tree problem
• Introduction to algorithms.
• New advances in reoptimizing the minimum Steiner tree problem
• New inapproximability bounds for TSP
• On the Hardness of Reoptimization
• Reoptimization in machine scheduling
• Reoptimization of NP-Hard Problems
• Reoptimization of Steiner Trees
• Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
• Reoptimization of Weighted Graph and Covering Problems
• Reoptimization of maximum weight induced hereditary subgraph problems
• Reoptimization of minimum and maximum traveling salesman's tours
• Reoptimization of the maximum weighted \(P_{k }\)-free subgraph problem under vertex insertion
• Reoptimization of the shortest common superstring problem
• Reoptimizing the 0-1 knapsack problem
• Reoptimizing the rural postman problem
• Reoptimizing the traveling salesman problem
• Scheduling with forbidden sets
• Simple and fast reoptimizations for the Steiner tree problem
• Steiner tree reoptimization in graphs with sharpened triangle inequality
• The saga of minimum spanning trees
• The traveling salesman problem and its variations

Cited in

(10)

• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem
• Heuristic reoptimization of time-extended multi-robot task allocation problems
• New algorithms for Steiner tree reoptimization
• New algorithms for Steiner tree reoptimization
• Submodular reassignment problem for reallocating agents to tasks with synergy effects
• Robust reoptimization of Steiner trees
• Reoptimizing the traveling salesman problem
• On solving travelling salesman problem with vertex requisitions
• Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications

This page was built for publication: A note on the traveling salesman reoptimization problem under vertex insertion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q483055)