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

Jaroslaw Byrka, Karen Aardal

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)
Original languageEnglish
Pages (from-to)379-384
Number of pages6
JournalOperations Research Letters
Issue number3
Publication statusPublished - 2007
Externally publishedYes

Bibliographical note

We consider the 1.52-approximation algorithm of Mahdian et al. for the metric uncapacitated facility location problem. Weshow that their algorithm does not close the gap with the lower bound on approximability, 1.463, by providing a constructionof instances for which its approximation ratio is not better than 1.494.


  • Facility location
  • Approximation algorithms
  • Analysis of algorithms

Cite this