The approximation gap for the metric facility location problem is not yet closed |
| |
| Authors: | Jaroslaw Byrka Karen Aardal |
| |
| Institution: | a CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands
b Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands |
| |
| 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. |
| |
| Keywords: | Facility location Approximation algorithms Analysis of algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
