| کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن | 
|---|---|---|---|---|
| 1142430 | 957148 | 2014 | 5 صفحه PDF | دانلود رایگان | 
عنوان انگلیسی مقاله ISI
												On the integrality ratio of the subtour LP for Euclidean TSP
												
											دانلود مقاله + سفارش ترجمه
													دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
																																												موضوعات مرتبط
												
													مهندسی و علوم پایه
													ریاضیات
													ریاضیات گسسته و ترکیبات
												
											پیش نمایش صفحه اول مقاله
												 
												چکیده انگلیسی
												A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is 4/34/3. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was 8/78/7. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.
ناشر
												Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 42, Issue 8, December 2014, Pages 495–499
											Journal: Operations Research Letters - Volume 42, Issue 8, December 2014, Pages 495–499
نویسندگان
												Stefan Hougardy,