An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization

DOI10.1137/1.9781611973730.50zbMath1371.90073arXiv1406.2951OpenAlexW2951012259MaRDI QIDQ5363039

Khoa Trinh, Jaroslaw Byrka, Aravind Srinivasan, Bartosz Rybicki, Thomas W. Pensyl

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.2951

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median, An Improved Approximation Algorithm for Knapsack Median Using Sparsification, Improved algorithms for joint optimization of facility locations and network connections, On stochastic \(k\)-facility location, An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation, Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties, Clustering through continuous facility location problems, LP-based approximation for uniform capacitated facility location problem, Probabilistic analysis of optimization problems on generalized random shortest path metrics, The distance-constrained matroid median problem, Efficient algorithms for fair clustering with a new notion of fairness, Ordinal approximation for social choice, matching, and facility location problems given candidate positions, Approximation algorithms for median hub location problems, Unnamed Item, Unnamed Item, Unnamed Item, A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem, An approximation algorithm for soft capacitated \(k\)-facility location problem, Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms, Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams, Polynomial time approximation schemes for clustering in low highway dimension graphs, Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics, Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median, Metric \(k\)-median clustering in insertion-only streams, An improved approximation algorithm for knapsack median using sparsification, Unnamed Item, Unnamed Item, A local search approximation algorithm for a squared metric \(k\)-facility location problem, Constant-Factor FPT Approximation for Capacitated k-Median, A Lottery Model for Center-Type Problems With Outliers, Approximation Algorithms for D-optimal Design, An approximation algorithm for stochastic multi-level facility location problem with soft capacities, To close is easier than to open: dual parameterization to \(k\)-median