A constant-factor approximation algorithm for the k-median problem
From MaRDI portal
A constant-factor approximation algorithm for the \(k\)-median problem
Recommendations
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
- scientific article; zbMATH DE number 1775394
- Clustering for metric and nonmetric distance measures
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
Cites work
- scientific article; zbMATH DE number 1670526 (Why is no real title available?)
- scientific article; zbMATH DE number 4202014 (Why is no real title available?)
- scientific article; zbMATH DE number 1187151 (Why is no real title available?)
- scientific article; zbMATH DE number 1305496 (Why is no real title available?)
- scientific article; zbMATH DE number 1559542 (Why is no real title available?)
- scientific article; zbMATH DE number 1775394 (Why is no real title available?)
- scientific article; zbMATH DE number 1775395 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- A Best Possible Heuristic for the k-Center Problem
- A new greedy approach for facility location problems
- A simple heuristic for the p-centre problem
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
- An approximation algorithm for the generalized assignment problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Approximation algorithms for geometric median problems
- Clustering to minimize the maximum intercluster distance
- Greedy Strikes Back: Improved Facility Location Algorithms
- How to Allocate Network Centers
- Local search heuristic for k-median and facility location problems
- The Capacitated K-Center Problem
Cited in
(92)- On clustering with discounts
- Probabilistic \(k\)-median clustering in data streams
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- Core-sets: updated survey
- scientific article; zbMATH DE number 7651196 (Why is no real title available?)
- scientific article; zbMATH DE number 2165699 (Why is no real title available?)
- scientific article; zbMATH DE number 7651148 (Why is no real title available?)
- scientific article; zbMATH DE number 7651201 (Why is no real title available?)
- Effective Heuristic Techniques for Combined Robust Clustering Problem
- \(k\)-median: exact recovery in the extended stochastic ball model
- New approximability results for the robust \(k\)-median problem
- Simpler and Better Algorithms for Minimum-Norm Load Balancing
- Interactive clustering of linear classes and cryptographic lower bounds
- Discrete facility location in machine learning
- Improved bounds for metric capacitated covering problems
- Approximation algorithms for robust clustering problems using local search techniques
- Hardness of approximation for Euclidean \(k\)-median
- Analysis of a local search algorithm for the \(k\)-facility location problem
- Parameterized complexity of categorical clustering with size constraints
- FPT Approximation for Constrained Metric k-Median/Means
- Covering a compact space by fixed-radius or growing random balls
- Data stability in clustering: a closer look
- Mobile facility location: combinatorial filtering via weighted occupancy
- Approximating k-median via pseudo-approximation
- The capacity constrained facility location problem
- Approximation Algorithms for the k-Median Problem
- Facility Location Problems: A Parameterized View
- Approximation algorithms for the lower-bounded knapsack median problem
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
- The median routing problem for simultaneous planning of emergency response and non-emergency jobs
- Incremental medians via online bidding
- Generalized \(k\)-means in GLMs with applications to the outbreak of COVID-19 in the United States
- Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
- scientific article; zbMATH DE number 1775394 (Why is no real title available?)
- Parameterized complexity of categorical clustering with size constraints
- An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
- Comparison and analysis of ten static heuristics-based Internet data replication techniques
- Approximating \(k\)-median via pseudo-approximation
- Approximation schemes for \(k\)-facility location
- The reverse greedy algorithm for the metric k-median problem
- An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
- Approximation algorithms for geometric median problems
- On the linear relaxation of the \(p\)-median problem
- An approximation algorithm for the \(p\)-hub median problem
- A local search approximation algorithm for a squared metric \(k\)-facility location problem
- Facility location problems: a parameterized view
- A new efficient algorithm based on DC programming and DCA for clustering
- Clustering for metric and nonmetric distance measures
- Clustering with or without the approximation
- A note on scenario reduction for two-stage stochastic programs
- Clustering through continuous facility location problems
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
- A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
- Local search algorithms for the red-blue median problem
- scientific article; zbMATH DE number 2090269 (Why is no real title available?)
- Locating depots for capacitated vehicle routing
- Approximating the \(\tau\)-relaxed soft capacitated facility location problem
- Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
- Facility Location with Matroid or Knapsack Constraints
- Multi-facility ordered median problems in directed networks
- Approximation algorithms for hierarchical location problems
- Lossy kernelization of same-size clustering
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
- Approximation algorithms for spherical \(k\)-means problem using local search scheme
- Lossy kernelization of same-size clustering
- A unified framework of FPT approximation algorithms for clustering problems
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Learning mixtures of separated nonspherical Gaussians
- An approximation algorithm for the continuous \(k\)-medians problem in a convex polygon
- The distance-constrained matroid median problem
- The Priority k-Median Problem
- Approximation algorithms for diversity-bounded center problems
- On the fixed-parameter tractability of capacitated clustering
- Constant factor approximation algorithm for the knapsack median problem
- A constant-factor approximation algorithm for the \(k\)-MST problem
- Most recent changepoint detection in censored panel data
- scientific article; zbMATH DE number 1256763 (Why is no real title available?)
- Centrality of trees for capacitated \(k\)-center
- Privacy preserving clustering with constraints
- Capacitated domination problem
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Constant-factor approximation for ordered \(k\)-median
- A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems
- A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem
- Maximum gradient embeddings and monotone clustering
- On the \(p\)-median polytope of \(Y\)-free graphs
- Approximation algorithms for the individually fair \(k\)-center with outliers
- Information-theoretic feature selection with discrete \(k\)-median clustering
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- Computing and Combinatorics
This page was built for publication: A constant-factor approximation algorithm for the \(k\)-median problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869938)
