A note on the traveling salesman reoptimization problem under vertex insertion

DOI10.1016/J.IPL.2014.11.003zbMATH Open1318.90061OpenAlexW1964618519MaRDI QIDQ483055FDOQ483055

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

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

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)

Cites Work

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

Cited In (10)

• 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
• Reoptimizing the traveling salesman problem
• Robust reoptimization of Steiner trees
• 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
• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem

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)