Better guarantees for \(k\)-median with service installation costs

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

zbMATH Keywords

clusteringapproximation\(k\)-median

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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