An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution

DOI10.1016/j.tcs.2018.02.026zbMath1408.90266OpenAlexW2794348239MaRDI QIDQ1630998

Da-Chuan Xu, Dong-lei Du, Chen-Chen Wu

Publication date: 5 December 2018

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

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

zbMATH Keywords

approximation algorithmpenaltypseudo-solution\(k\)-median problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search algorithms for the red-blue median problem
• An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Approximation algorithms for geometric median problems
• A constant-factor approximation algorithm for the \(k\)-median problem
• 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
• A new greedy approach for facility location problems
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Local Search Heuristics for k-Median and Facility Location Problems
• Approximating k-median via pseudo-approximation