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
- 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 O(pn^ 2) algorithm for the p-median and related problems on tree graphs
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- 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
- 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?)
- Local search heuristic for k-median and facility location problems
- The Capacitated K-Center Problem
Cited in
(only showing first 100 items - show all)- The reverse greedy algorithm for the metric k-median problem
- Approximation algorithms for geometric median problems
- A constant-factor approximation algorithm for the \(k\)-MST problem
- An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
- Information-theoretic feature selection with discrete \(k\)-median clustering
- 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
- Learning mixtures of separated nonspherical Gaussians
- Maximum gradient embeddings and monotone clustering
- Most recent changepoint detection in censored panel data
- Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
- Approximating the \(\tau\)-relaxed soft capacitated facility location problem
- Approximation algorithms for the lower-bounded knapsack median problem
- Lossy kernelization of same-size clustering
- Improved approximation algorithms for solving the squared metric k-facility location problem
- The distance-constrained matroid median problem
- The median routing problem for simultaneous planning of emergency response and non-emergency jobs
- The capacity constrained facility location problem
- Approximation algorithms for spherical \(k\)-means problem using local search scheme
- Mobile facility location: combinatorial filtering via weighted occupancy
- Facility location problems: a parameterized view
- Partial recovery bounds for clustering with the relaxed K-means
- Probabilistic k-median clustering in data streams
- Clustering with or without the approximation
- A new efficient algorithm based on DC programming and DCA for clustering
- An approximation algorithm for the \(p\)-hub median problem
- A note on scenario reduction for two-stage stochastic programs
- Incremental medians via online bidding
- On clustering with discounts
- Approximating k-median via pseudo-approximation
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
- Interactive clustering of linear classes and cryptographic lower bounds
- Clustering for metric and nonmetric distance measures
- An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
- An approximation algorithm for the continuous k-medians problem in a convex polygon
- Locating depots for capacitated vehicle routing
- Analysis of a local search algorithm for the k-facility location problem
- New approximability results for the robust k-median problem
- Core-sets: updated survey
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Clustering through continuous facility location problems
- Facility Location Problems: A Parameterized View
- scientific article; zbMATH DE number 1256763 (Why is no real title available?)
- On the linear relaxation of the \(p\)-median problem
- Comparison and analysis of ten static heuristics-based Internet data replication techniques
- scientific article; zbMATH DE number 1775394 (Why is no real title available?)
- Data stability in clustering: a closer look
- scientific article; zbMATH DE number 2165699 (Why is no real title available?)
- scientific article; zbMATH DE number 2090269 (Why is no real title available?)
- Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
- Privacy preserving clustering with constraints
- Simpler and Better Algorithms for Minimum-Norm Load Balancing
- On the fixed-parameter tractability of capacitated clustering
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- Covering a compact space by fixed-radius or growing random balls
- Discrete facility location in machine learning
- Constant-factor approximation for ordered k-median
- Facility Location with Matroid or Knapsack Constraints
- Capacitated domination problem
- A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
- Approximation Algorithms for the k-Median Problem
- Multi-facility ordered median problems in directed networks
- The Priority k-Median Problem
- Approximating k-median via pseudo-approximation
- Computing and Combinatorics
- Constant factor approximation algorithm for the knapsack median problem
- Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
- scientific article; zbMATH DE number 7651148 (Why is no real title available?)
- scientific article; zbMATH DE number 7651196 (Why is no real title available?)
- scientific article; zbMATH DE number 7651201 (Why is no real title available?)
- A local search approximation algorithm for a squared metric \(k\)-facility location problem
- Approximation algorithms for hierarchical location problems
- 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
- A unified framework of FPT approximation algorithms for clustering problems
- Hardness of approximation for Euclidean \(k\)-median
- FPT Approximation for Constrained Metric k-Median/Means
- Parameterized complexity of categorical clustering with size constraints
- 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
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- Approximation schemes for k-facility location
- Lossy kernelization of same-size clustering
- Approximation algorithms for robust clustering problems using local search techniques
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Baby PIH: Parameterized inapproximability of min CSP
- Parameterized inapproximability hypothesis under ETH
- Improved approximation algorithm for individual fairness k-median
- Online k-Median with consistent clusters
- Local search algorithms for the red-blue median problem
- Clustering what matters in constrained settings (improved outlier to outlier-free reductions)
- Clustering what matters in constrained settings: improved outlier to outlier-free reductions
- Improved polynomial-time approximations for clustering with minimum sum of radii or diameters
- Approximation algorithms for continuous clustering and facility location problems
- Optimal algorithms for multiwinner elections and the Chamberlin-Courant rule
- Better guarantees for individual fairness k-median
- Approximation algorithms for clustering with minimum sum of radii, diameters, and squared radii
- Generalized k-means in GLMs with applications to the outbreak of COVID-19 in the United States
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)
