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

DOI10.1137/1.9781611973730.50MaRDI QIDQ5363039zbMATH OpenOpenAlexFDO

Authors Jaroslaw Byrka, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh, 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) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Abstract: Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to emph{negative correlation} properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires emph{positive} correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior - near-independence, which generalizes positive correlation - on "small" subsets of the variables. The recent breakthrough of Li & Svensson for the classical $k$-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for $k$-median from $2.732+epsilon$ to $2.675+epsilon$ by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter $epsilon$ from Li-Svensson's $N^{O(1/epsilo{n}^2)}$ to $N^{O((1/epsilon)log(1/epsilon))}$.

Recommendations

• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Improved parameterized approximation for balanced \(k\)-median
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• Approximate solution of the \(p\)-median minimization problem
• Approximating k-median via pseudo-approximation
• Approximating k-median via pseudo-approximation
• Improved Approximation Algorithms for Budgeted Allocations
• Approximate positive correlated distributions and approximation algorithms for D-optimal design

Cited in

(38)

• A local search approximation algorithm for the uniform capacitated k-facility location problem
• An approximation algorithm for soft capacitated k-facility location problem
• An improved approximation algorithm for knapsack median using sparsification
• 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
• On stochastic k-facility location
• LP-based approximation for uniform capacitated facility location problem
• The distance-constrained matroid median problem
• Ordinal approximation for social choice, matching, and facility location problems given candidate positions
• Polynomial time approximation schemes for clustering in low highway dimension graphs
• Metric \(k\)-median clustering in insertion-only streams
• Approximation algorithms for median hub location problems
• Accurate low-space approximation of metric k-median for insertion-only streams
• An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
• Improved algorithms for joint optimization of facility locations and network connections
• Approximation algorithms for \(D\)-optimal design
• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
• An improved approximation algorithm for knapsack median using sparsification
• Clustering through continuous facility location problems
• Local search algorithms for \(k\)-median and \(k\)-facility location problems with linear penalties
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• A Lottery Model for Center-Type Problems With Outliers
• Proportional approval voting, harmonic \(k\)-median, and negative association
• Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
• Constant-Factor FPT Approximation for Capacitated k-Median
• Robust communication-optimal distributed clustering algorithms
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Polynomial time approximation schemes for clustering in low highway dimension graphs
• scientific article; zbMATH DE number 7650129 (Why is no real title available?)
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• Efficient algorithms for fair clustering with a new notion of fairness
• Approximation algorithms for robust clustering problems using local search techniques
• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
• Fitting distances by tree metrics minimizing the total error within a constant factor
• Competitive ratio vs regret minimization: achieving the best of both worlds
• FPT approximations for fair k-min-sum-radii

This page was built for publication: An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization

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