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

DOI10.1016/J.TCS.2018.02.026MaRDI QIDQ1630998zbMATH OpenOpenAlexWikidataFDO

Authors Chenchen Wu, Donglei Du, Dachuan Xu

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) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
• Approximating \(k\)-median via pseudo-approximation
• Approximating k-median via pseudo-approximation
• Approximation Algorithms for the k-Median Problem
• An improved approximation algorithm for the hard uniform capacitated \(k\)-median problem
• A constant-factor approximation algorithm for the k-median problem
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• An approximation algorithm for the \(p\)-hub median problem
• An approximation algorithm for uniform capacitated \(k\)-median problem with \(1+\epsilon\) capacity violation

Cites work

• scientific article; zbMATH DE number 1303608 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• A constant-factor approximation algorithm for the k-median problem
• A new greedy approach for facility location problems
• Algorithms for facility location problems with outliers. (Extended abstract)
• An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
• Approximating k-median via pseudo-approximation
• Approximation algorithms for geometric median problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Local Search Heuristics for k-Median and Facility Location Problems
• Local search algorithms for the red-blue median problem

Cited in

(7)

• Approximating k-median via pseudo-approximation
• Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
• Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
• Approximating \(k\)-median via pseudo-approximation
• An improved approximation algorithm for squared metric \(k\)-facility location
• An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
• Better guarantees for \(k\)-median with service installation costs

This page was built for publication: An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution

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