Name
Abstract | ||
|---|---|---|
We propose a 43-approximation in linear time for the metric traveling salesman reoptimization problem under vertex insertion. This constitutes an improvement of the time complexity of the best known existing bound since in Ausiello et al. (2009) [5] a 4/3-approximation is already given with a complexity O(n3). Our algorithm is of independent interest because it does not use a matching to build the approximate solution. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.ipl.2014.11.003 | Information Processing Letters |
Keywords | Field | DocType |
Approximation algorithms,Reoptimization under vertex insertion,TSP | Discrete mathematics,Approximation algorithm,Combinatorics,Vertex (geometry),Travelling salesman problem,Time complexity,Approximate solution,Mathematics | Journal |
Volume | Issue | ISSN |
115 | 3 | 0020-0190 |
Citations | PageRank | References |
5 | 0.42 | 24 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jérôme Monnot | 1 | 512 | 55.74 |