An improved approximation algorithm for squared metric \(k\)-facility location

DOI10.1007/978-3-030-92681-6_42OpenAlexW4206792503MaRDI QIDQ2150578

Qilong Feng, Zhen Zhang

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_42

zbMATH Keywords

approximation algorithm\(k\)-meanssquared metric \(k\)-facility location

Mathematics Subject Classification ID

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