Back to Search
Start Over
Improved approximation algorithms for solving the squared metric k-facility location problem.
- Source :
-
Theoretical Computer Science . Jan2023, Vol. 942, p107-122. 16p. - Publication Year :
- 2023
-
Abstract
- The squared metric k -facility location problem is a frequently encountered generalization of the k -means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44.473 + ϵ , which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36.342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric. • We give a (36.342 + ϵ) -approximation algorithm for the squared metric k -facility location problem. • We obtain a well-behaved fractional solution to the squared metric k -facility location problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach that exploits the properties of the squared metric. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 942
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 160888461
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.11.027