A constant-factor approximation algorithm for the \(k\)-median problem
From MaRDI portal
Publication:1869938
DOI10.1006/jcss.2002.1882zbMath1023.90037OpenAlexW2085751730WikidataQ56519776 ScholiaQ56519776MaRDI QIDQ1869938
Sudipto Guha, David B. Shmoys, Moses Charikar, Éva Tardos
Publication date: 4 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2002.1882
Discrete location and assignment (90B80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (69)
Generalized \(k\)-means in GLMs with applications to the outbreak of COVID-19 in the United States ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ Clustering with or without the approximation ⋮ Information-theoretic feature selection with discrete \(k\)-median clustering ⋮ A new efficient algorithm based on DC programming and DCA for clustering ⋮ Analysis of a local search algorithm for the k-facility location problem ⋮ On generalizations of network design problems with degree bounds ⋮ The distance-constrained matroid median problem ⋮ The median routing problem for simultaneous planning of emergency response and non-emergency jobs ⋮ Discrete facility location in machine learning ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ Effective Heuristic Techniques for Combined Robust Clustering Problem ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Improved bounds for metric capacitated covering problems ⋮ A parameterized approximation algorithm for the multiple allocation \(k\)-hub center ⋮ Approximation algorithms for diversity-bounded center problems ⋮ An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Facility Location Problems: A Parameterized View ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation schemes for \(k\)-facility location ⋮ An Approximation Algorithm for the Continuous k-Medians Problem in a Convex Polygon ⋮ Maximum gradient embeddings and monotone clustering ⋮ On the linear relaxation of the \(p\)-median problem ⋮ A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem ⋮ Comparison and analysis of ten static heuristics-based Internet data replication techniques ⋮ The capacity constrained facility location problem ⋮ Data stability in clustering: a closer look ⋮ Approximation algorithms for spherical \(k\)-means problem using local search scheme ⋮ Core-Sets: Updated Survey ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ A note on scenario reduction for two-stage stochastic programs ⋮ On the \(p\)-median polytope of \(Y\)-free graphs ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Most recent changepoint detection in censored panel data ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ Local search algorithms for the red-blue median problem ⋮ Capacitated domination problem ⋮ Incremental medians via online bidding ⋮ Covering a compact space by fixed-radius or growing random balls ⋮ Multi-facility ordered median problems in directed networks ⋮ Learning mixtures of separated nonspherical Gaussians ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations ⋮ Lossy kernelization of same-size clustering ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Facility location problems: a parameterized view ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A local search approximation algorithm for a squared metric \(k\)-facility location problem ⋮ Approximation algorithms for the lower-bounded knapsack median problem ⋮ Approximating $k$-Median via Pseudo-Approximation ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ Locating Depots for Capacitated Vehicle Routing ⋮ Approximation algorithms for hierarchical location problems ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ Partial recovery bounds for clustering with the relaxed \(K\)-means ⋮ Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple heuristic for the p-centre problem
- Clustering to minimize the maximum intercluster distance
- Approximation algorithms for geometric median problems
- An approximation algorithm for the generalized assignment problem
- An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
- A new greedy approach for facility location problems
- A Best Possible Heuristic for the k-Center Problem
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- Greedy Strikes Back: Improved Facility Location Algorithms
- How to Allocate Network Centers
- The Capacitated K-Center Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Local search heuristic for k-median and facility location problems
This page was built for publication: A constant-factor approximation algorithm for the \(k\)-median problem
