An approximation algorithm for the k-median problem with uniform penalties via pseudo-solution
DOI10.1016/J.TCS.2018.02.026zbMATH Open1408.90266OpenAlexW2794348239WikidataQ130161966 ScholiaQ130161966MaRDI QIDQ1630998FDOQ1630998
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
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
Combinatorial optimization (90C27) Approximation algorithms (68W25) Discrete location and assignment (90B80)
Cites Work
- Approximating k-median via pseudo-approximation
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Algorithms for facility location problems with outliers. (Extended abstract)
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Title not available (Why is that?)
- A new greedy approach for facility location problems
- Title not available (Why is that?)
- Local Search Heuristics for k-Median and Facility Location Problems
- Local search algorithms for the red-blue median problem
- A constant-factor approximation algorithm for the \(k\)-median problem
- Improved approximation algorithms for the facility location problems with linear/submodular penalties
- Approximation algorithms for geometric median problems
- An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
Cited In (7)
- Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
- Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
- 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
- Approximating k-median via pseudo-approximation
- 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)
