Better guarantees for \(k\)-median with service installation costs
From MaRDI portal
Publication:2672628
DOI10.1016/j.tcs.2022.05.014OpenAlexW4280576712MaRDI QIDQ2672628
Zhen Zhang, Shao-qian Yu, Yipeng Zhou
Publication date: 13 June 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.05.014
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithm for facility location with service installation costs
- An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
- Some heuristic methods for solving \(p\)-median problems with a coverage constraint
- An improved approximation algorithm for the \(k\)-means problem with penalties
- Solving the \(p\)-median problem on regular and lattice networks
- Approximating $k$-Median via Pseudo-Approximation
- Approximation Algorithms for Data Placement Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Linear-time approximation schemes for clustering problems in any dimensions
- On k-Median clustering in high dimensions
- Greedy Strikes Back: Improved Facility Location Algorithms
- Local Search Yields a PTAS for $k$-Means in Doubling Metrics
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- A Bi-Criteria Approximation Algorithm for k-Means
- Local Search Heuristics for k-Median and Facility Location Problems
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- Near-linear Time Approximation Schemes for Clustering in Doubling Metrics
- Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
- Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering
- Non-metric Multicommodity and Multilevel Facility Location
- A unified framework of FPT approximation algorithms for clustering problems