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

DOI10.1016/J.TCS.2022.11.027MaRDI QIDQ2110368zbMATH OpenOpenAlexFDO

Authors Zhen Zhang, Qilong Feng, Junyu Huang, 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

approximation algorithmLagrangian relaxationsquared metric \(k\)-facility location

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• Approximation algorithms for the squared metric k-level facility location problem
• Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
• An approximation algorithm for the squared metric dynamic facility location problem

Cites work

• \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A constant-factor approximation algorithm for the k-median problem
• A dependent LP-rounding approach for the k-median problem
• A local search approximation algorithm for \(k\)-means clustering
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• A new approximation algorithm for the k-facility location problem
• A simple tabu search for warehouse location
• Algorithms for facility location problems with outliers. (Extended abstract)
• 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
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• Approximation algorithm for squared metric two-stage stochastic facility location problem
• Approximation Algorithms for Aversion k-Clustering via Local k-Median
• Approximation algorithms for data placement on parallel disks
• Approximation Algorithms for Data Placement Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved approximation for prize-collecting red-blue median
• Local search algorithms for the red-blue median problem
• Local Search Heuristics for k-Median and Facility Location Problems

Cited in

(3)

• The approximation gap for the metric facility location problem is not yet closed
• A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties
• Better guarantees for individual fairness k-median

Describes a project that uses

Uses Software

• k-means++

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2110368)