کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6895152 | 1445938 | 2018 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
ترجمه فارسی عنوان
مرزهای بالایی شکاف یکپارچگی برای مشکلات مسافرتی با فاصله های یک و دو بهبود یافته است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
فروشنده مسافرتی، شکاف یکپارچگی، حذف زیرزمینی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We prove these bounds by providing local search algorithms that, in polynomial time, find 2-matchings with few components in the support of the solution. We show that the run times of our algorithms cannot be considerably improved under standard complexity-theoretic assumptions: we show that finding improved TSP solutions via local search is intractable for edge change parameterized by the size of the neighborhoods even for instances with distances one and two; this strengthens a result of Dániel Marx.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 266, Issue 2, 16 April 2018, Pages 436-457
Journal: European Journal of Operational Research - Volume 266, Issue 2, 16 April 2018, Pages 436-457
نویسندگان
Matthias Mnich, Tobias Mömke,