کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436371 689996 2008 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A better differential approximation ratio for symmetric TSP
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A better differential approximation ratio for symmetric TSP
چکیده انگلیسی

In this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to 3/4−ε (for any ε>0) the best differential ratio of 2/3 known so far, given in Hassin and Khuller, [R. Hassin, S. Khuller, z-approximations, J. Algorithms, 41 (2) (2001) 429–442].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 396, Issues 1–3, 10 May 2008, Pages 63-70