Approximating k-median via pseudo-approximation

DOI10.1137/130938645MaRDI QIDQ2805513zbMATH OpenOpenAlexFDO

Authors Shi Li, Ola Svensson

Publication date 12 May 2016

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-medianapproximation algorithmpseudo-approximation

Mathematics Subject Classification ID

Approximation algorithms (68W25) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Abstract: We present a novel approximation algorithm for $k$-median that achieves an approximation guarantee of $1+sqrt3+epsilon$, improving upon the decade-old ratio of $3+epsilon$. Our approach is based on two components, each of which, we believe, is of independent interest. First, we show that in order to give an $alpha$-approximation algorithm for $k$-median, it is sufficient to give a emph{pseudo-approximation algorithm} that finds an $alpha$-approximate solution by opening $k+O(1)$ facilities. This is a rather surprising result as there exist instances for which opening $k+1$ facilities may lead to a significant smaller cost than if only $k$ facilities were opened. Second, we give such a pseudo-approximation algorithm with $alpha=1+sqrt3+epsilon$. Prior to our work, it was not even known whether opening $k+o(k)$ facilities would help improve the approximation ratio.

Recommendations

• Approximating k-median via pseudo-approximation
• An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
• An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
• A dependent LP-rounding approach for the k-median problem
• Approximation Algorithms for the k-Median Problem

Cites work

• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• A constant-factor approximation algorithm for the k-median problem
• A dependent LP-rounding approach for the k-median problem
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A new greedy approach for facility location problems
• An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximating k-median with non-uniform capacities
• Approximation algorithms for geometric median problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation Algorithms for Metric Facility Location Problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Combinatorial Algorithms for Facility Location Problems
• Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties
• Local Search Heuristics for k-Median and Facility Location Problems
• Mathematical Programming for Data Mining: Formulations and Challenges

Cited in

(61)

• An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
• A local search approximation algorithm for the uniform capacitated k-facility location problem
• Faster balanced clusterings in high dimension
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• Approximation algorithms for the lower-bounded knapsack median problem
• An approximation algorithm for stochastic multi-level facility location problem with soft capacities
• Lossy kernelization of same-size clustering
• Improved approximation algorithms for solving the squared metric k-facility location problem
• On parameterized approximation algorithms for balanced clustering
• Problem-based optimal scenario generation and reduction in stochastic programming
• Scenario reduction revisited: fundamental limits and guarantees
• An improved approximation algorithm for capacitated correlation clustering problem
• An improved approximation algorithm for squared metric \(k\)-facility location
• Improved parameterized approximation for balanced \(k\)-median
• An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee
• Approximation algorithms for clustering with dynamic points
• The distance-constrained matroid median problem
• Approximation algorithms for spherical \(k\)-means problem using local search scheme
• Iterative partial rounding for vertex cover with hard capacities
• The ordered \(k\)-median problem: surrogate models and approximation algorithms
• Local search approximation algorithms for the k-means problem with penalties
• Solving the \(p\)-median problem on regular and lattice networks
• On clustering with discounts
• Better guarantees for \(k\)-median with service installation costs
• An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
• Kantorovich-Rubinstein distance minimization: application to location problems
• Approximation algorithms for distributed multi-robot coverage in non-convex environments
• A lower bound for metric 1-median selection
• Finding the Median (Obliviously) with Bounded Space
• A branch decomposition algorithm for the p-median problem
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
• scientific article; zbMATH DE number 2165699 (Why is no real title available?)
• Privacy preserving clustering with constraints
• 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
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• scientific article; zbMATH DE number 7651196 (Why is no real title available?)
• On the cost of essentially fair clusterings
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• A unified framework of FPT approximation algorithms for clustering problems
• Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
• FPT Approximation for Constrained Metric k-Median/Means
• Lossy kernelization of same-size clustering
• An improved approximation algorithm for the capacitated correlation clustering problem
• A local search algorithm for radius-constrained k-median
• Approximation algorithms for robust clustering problems using local search techniques
• Baby PIH: Parameterized inapproximability of min CSP
• An o( n)-approximation for submodular facility location
• Parameterized inapproximability hypothesis under ETH
• Improved approximation algorithm for individual fairness k-median
• Online k-Median with consistent clusters
• Polynomial-time approximation schemes for facility location on planar graphs
• Structural iterative rounding for generalized k-median problems
• FPT approximation for fair minimum-load clustering
• Approximation algorithms for continuous clustering and facility location problems
• A local search algorithm for the radius-constrained k-median problem
• Better guarantees for individual fairness k-median
• Structural iterative rounding for generalized \(k\)-median problems
• Relational algorithms for k-means clustering

This page was built for publication: Approximating \(k\)-median via pseudo-approximation

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