کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141868 957096 2011 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
چکیده انگلیسی

Consider the traveling salesman problem (TSP) defined on the complete graph, where the edge costs satisfy the triangle inequality. Let TOUR denote the optimal solution value for the TSP. Two well-known relaxations of the TSP are the subtour elimination problem and the 2-matching problem. If we let SUBT and 2M represent the optimal solution values for these two relaxations, then it has been conjectured that TOUR/SUBT ≤4/3≤4/3, and that 2M/SUBT ≤10/9≤10/9.In this paper, we exploit the structure of certain 1/21/2-integer solutions for the subtour elimination problem in order to obtain low cost TSP and 2-matching solutions. In particular, we show that for cost functions for which the optimal subtour elimination solution found falls into our classes, the above two conjectures are true. Our proofs are constructive and could be implemented in polynomial time, and thus, for such cost functions, provide a 4/3 (or better) approximation algorithm for the TSP.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 8, Issue 4, November 2011, Pages 525–539
نویسندگان
, ,