Improved approximation algorithms for solving the squared metric \(k\)-facility location problem

DOI10.1016/j.tcs.2022.11.027OpenAlexW4310142618MaRDI QIDQ2110368

Junyu Huang, Qilong Feng, Zhen Zhang, Jianxin Wang

Publication date: 21 December 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.11.027

zbMATH Keywords

Lagrangian relaxationapproximation algorithmsquared metric \(k\)-facility location

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties

Uses Software

• k-means++

Cites Work

• Unnamed Item
• 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
• An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
• A constant-factor approximation algorithm for the \(k\)-median problem
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Improved approximation for prize-collecting red-blue median
• \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
• An improved approximation algorithm for the \(k\)-means problem with penalties
• A new approximation algorithm for the \(k\)-facility location problem
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• Approximation algorithm for squared metric two-stage stochastic facility location problem
• Approximating $k$-Median via Pseudo-Approximation
• A Dependent LP-Rounding Approach for the k-Median Problem
• Approximation Algorithms for Data Placement Problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Approximation Algorithms for Aversion k-Clustering via Local k-Median
• 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

This page was built for publication: Improved approximation algorithms for solving the squared metric \(k\)-facility location problem