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

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
نویسندگان
, ,