کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428896 | 686958 | 2015 | 4 صفحه PDF | دانلود رایگان |
• 4/3-approximation for the metric traveling salesman reoptimization problem under vertex insertion in linear time.
• This is an improvement of the complexity-time of the best known existing bound.
• This result is of interest independently because it does not use the help of a matching for building the approximate solution.
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)O(n3). Our algorithm is of independent interest because it does not use a matching to build the approximate solution.
Journal: Information Processing Letters - Volume 115, Issue 3, March 2015, Pages 435–438