Bansal, Manisha ; Garg, Naveen ; Gupta, Neelima (2012) A 5-approximation for capacitated facility location In: ESA'12 Proceedings of the 20th Annual European Conference on Algorithms, September 10-12, 2012, Ljubljana, Slovenia.
Full text not available from this repository.
Official URL: https://link.springer.com/chapter/10.1007/978-3-64...
Abstract
In this paper, we propose and analyze a local search algorithm for the capacitated facility location problem. Our algorithm is a modification of the algorithm proposed by Zhang et al. [7] and improves the approximation ratio from 5.83 to 5. We achieve this by modifying the close, open and multi operations. The idea of taking linear combinations of inequalities used in Aggarwal et al [1] is crucial in achieving this result. The example proposed by Zhang et al. also shows that our analysis is tight.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Springer Verlag. |
| ID Code: | 101287 |
| Deposited On: | 31 Jan 2018 09:33 |
| Last Modified: | 31 Jan 2018 09:33 |
Repository Staff Only: item control page
