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

0.00 Avg rating—0 Votes
Article ID: iaor20082197
Country: Netherlands
Volume: 35
Issue: 3
Start Page Number: 379
End Page Number: 384
Publication Date: May 2007
Journal: Operations Research Letters
Authors: ,
Keywords: computational analysis
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.