کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1143301 | 957189 | 2007 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The approximation gap for the metric facility location problem is not yet closed
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider the 1.521.52-approximation algorithm of Mahdian et al. for the metric uncapacitated facility location problem. We show that their algorithm does not close the gap with the lower bound on approximability, 1.4631.463, by providing a construction of instances for which its approximation ratio is not better than 1.4941.494.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 35, Issue 3, May 2007, Pages 379–384
Journal: Operations Research Letters - Volume 35, Issue 3, May 2007, Pages 379–384
نویسندگان
Jaroslaw Byrka, Karen Aardal,