کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
710045 | 892102 | 2016 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial Time Approximation Scheme for the Minimum-weight k-Size Cycle Cover Problem in Euclidean space of an arbitrary fixed dimension
ترجمه فارسی عنوان
طرح تقریبی زمان چندجملهای برای پوشش کمینه چرخه کره اندازه ی کوچک در فضای اقلیدسی یک بعد ثابت دلخواه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پوشش چرخه اندازه k؛ مسئله فروشنده دورهگرد (TSP)؛ مشکل NP سخت طرح تقریبی چندجمله ای (PTAS)
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مکانیک محاسباتی
چکیده انگلیسی
We study the Min-k-SCCP on the partition of a complete weighted digraph by k vertex-disjoint cycles of minimum total weight. This problem is the generalization of the well-known traveling salesman problem (TSP) and the special case of the classical vehicle routing problem (VRP). It is known that the problem Min-k-SCCP is strongly NP-hard and remains intractable even in the geometric statement. For the Euclidean Min-k-SCCP in Rd, we construct a polynomial-time approximation scheme, which generalizes the approach proposed earlier for the planar Min-2-SCCP. For any fixed c > 1, the scheme finds a (1 + 1/c)-approximate solution in time of O(nd+1(k log n)(O (√dc))d-1 2k).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: IFAC-PapersOnLine - Volume 49, Issue 12, 2016, Pages 6–10
Journal: IFAC-PapersOnLine - Volume 49, Issue 12, 2016, Pages 6–10
نویسندگان
Michael Khachay, Katherine Neznakhina,