An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions

DOI10.1007/978-3-319-48749-6_39zbMath1408.90265OpenAlexW2544022046MaRDI QIDQ2958344

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

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_39

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search algorithms for the red-blue median problem
• 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
• Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties
• 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

This page was built for publication: An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions