Approximating $k$-Median via Pseudo-Approximation
From MaRDI portal
Publication:2805513
DOI10.1137/130938645zbMath1338.90346arXiv1211.0243OpenAlexW2343942810MaRDI QIDQ2805513
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
Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (37)
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 ⋮ A lower bound for metric 1-median selection ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ Approximation algorithms for clustering with dynamic points ⋮ Solving the \(p\)-median problem on regular and lattice networks ⋮ The distance-constrained matroid median problem ⋮ On clustering with discounts ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ A Branch Decomposition Algorithm for the p-Median Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ Approximation algorithms for spherical \(k\)-means problem using local search scheme ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Kantorovich–Rubinstein Distance Minimization: Application to Location Problems ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ On the cost of essentially fair clusterings ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ Faster balanced clusterings in high dimension ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ A local search approximation algorithm for a squared metric \(k\)-facility location problem ⋮ Approximation algorithms for the lower-bounded knapsack median problem ⋮ Approximation Algorithms for Distributed Multi-robot Coverage in Non-convex Environments ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ Lossy kernelization of same-size clustering ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation algorithms for geometric median problems
- A constant-factor approximation algorithm for the \(k\)-median problem
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- A Dependent LP-Rounding Approach for the k-Median Problem
- A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Approximation Algorithms for Metric Facility Location Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A new greedy approach for facility location problems
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Local Search Heuristics for k-Median and Facility Location Problems
- Mathematical Programming for Data Mining: Formulations and Challenges
- Improved Combinatorial Algorithms for Facility Location Problems
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
- Algorithms - ESA 2003
This page was built for publication: Approximating $k$-Median via Pseudo-Approximation
