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
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
