The approximation gap for the metric facility location problem is not yet closed

✍ Scribed by Jaroslaw Byrka; Karen Aardal

• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 150 KB
• Volume: 35
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2006.03.017

✦ Synopsis

We consider the 1.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.463, by providing a construction of instances for which its approximation ratio is not better than 1.494.