An improved approximation algorithm for squared metric \(k\)-facility location
From MaRDI portal
Publication:2150578
DOI10.1007/978-3-030-92681-6_42OpenAlexW4206792503MaRDI QIDQ2150578
Publication date: 29 June 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_42
Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A local search approximation algorithm for \(k\)-means clustering
- Local search algorithms for the red-blue median problem
- A simple tabu search for warehouse location
- A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
- NP-hardness of Euclidean sum-of-squares clustering
- An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
- An improved approximation algorithm for the \(k\)-means problem with penalties
- A new approximation algorithm for the \(k\)-facility location problem
- Approximating $k$-Median via Pseudo-Approximation
- A Dependent LP-Rounding Approach for the k-Median Problem
- Approximation algorithms for data placement on parallel disks
- Approximation Algorithms for Data Placement Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Greedy Strikes Back: Improved Facility Location Algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Approximation Algorithms for Aversion k-Clustering via Local k-Median
- Local Search Yields a PTAS for $k$-Means in Doubling Metrics
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Local Search Heuristics for k-Median and Facility Location Problems
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
- A local search approximation algorithm for a squared metric \(k\)-facility location problem