Approximating k-median via pseudo-approximation
From MaRDI portal
Publication:2805513
DOI10.1137/130938645zbMATH Open1338.90346arXiv1211.0243OpenAlexW2343942810MaRDI QIDQ2805513FDOQ2805513
Authors: Shi Li, Ola Svensson
Publication date: 12 May 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Abstract: We present a novel approximation algorithm for -median that achieves an approximation guarantee of , improving upon the decade-old ratio of . 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 -approximation algorithm for -median, it is sufficient to give a emph{pseudo-approximation algorithm} that finds an -approximate solution by opening facilities. This is a rather surprising result as there exist instances for which opening facilities may lead to a significant smaller cost than if only facilities were opened. Second, we give such a pseudo-approximation algorithm with . Prior to our work, it was not even known whether opening facilities would help improve the approximation ratio.
Full work available at URL: https://arxiv.org/abs/1211.0243
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
Combinatorial optimization (90C27) Approximation algorithms (68W25) Discrete location and assignment (90B80)
Cites Work
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Title not available (Why is that?)
- An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
- A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
- Improved Combinatorial Algorithms for Facility Location Problems
- A dependent LP-rounding approach for the \(k\)-median problem
- A new greedy approach for facility location problems
- Approximation Algorithms for Metric Facility Location Problems
- Local Search Heuristics for k-Median and Facility Location Problems
- Mathematical Programming for Data Mining: Formulations and Challenges
- Analysis of a Local Search Heuristic for Facility Location Problems
- A constant-factor approximation algorithm for the \(k\)-median problem
- Approximating \(k\)-median with non-uniform capacities
- Approximation algorithms for geometric median problems
- Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties
Cited In (48)
- Finding the Median (Obliviously) with Bounded Space
- An improved approximation algorithm for capacitated correlation clustering problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
- Iterative partial rounding for vertex cover with hard capacities
- The ordered \(k\)-median problem: surrogate models and approximation algorithms
- On parameterized approximation algorithms for balanced clustering
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
- A unified framework of FPT approximation algorithms for clustering problems
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Approximation algorithms for spherical \(k\)-means problem using local search scheme
- Solving the \(p\)-median problem on regular and lattice networks
- Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
- On the cost of essentially fair clusterings
- Local search approximation algorithms for the \(k\)-means problem with penalties
- Approximation algorithms for clustering with dynamic points
- An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee
- An improved approximation algorithm for the capacitated correlation clustering problem
- Faster balanced clusterings in high dimension
- FPT Approximation for Constrained Metric k-Median/Means
- An improved approximation algorithm for squared metric \(k\)-facility location
- Improved parameterized approximation for balanced \(k\)-median
- Approximation algorithms for the lower-bounded knapsack median problem
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Title not available (Why is that?)
- An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
- On clustering with discounts
- A local search algorithm for radius-constrained \(k\)-median
- Approximation algorithms for robust clustering problems using local search techniques
- A lower bound for metric 1-median selection
- Scenario reduction revisited: fundamental limits and guarantees
- Approximation algorithms for distributed multi-robot coverage in non-convex environments
- The distance-constrained matroid median problem
- A local search approximation algorithm for a squared metric \(k\)-facility location problem
- A branch decomposition algorithm for the \(p\)-median problem
- An approximation algorithm for stochastic multi-level facility location problem with soft capacities
- A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem
- Privacy preserving clustering with constraints
- Problem-based optimal scenario generation and reduction in stochastic programming
- Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
- Kantorovich-Rubinstein distance minimization: application to location problems
- Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
- Approximating k-median via pseudo-approximation
- Better guarantees for \(k\)-median with service installation costs
- Lossy kernelization of same-size clustering
- Lossy kernelization of same-size 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)