A constant-factor approximation algorithm for the k -median problem (extended abstract)

DOI10.1145/301250.301257zbMath1346.68253OpenAlexW2023770210MaRDI QIDQ2819529

David B. Shmoys, Sudipto Guha, Éva Tardos, Moses Charikar

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301257

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Universal Algorithms for Clustering Problems, Capacitated facility location with outliers/penalties, Complex tilings, The \(k\)-centrum multi-facility location problem, Communication preserving protocols for secure function evaluation, A sieve algorithm for the shortest lattice vector problem, Fast computation of low rank matrix approximations, Spectral analysis of data, Optimal outlier removal in high-dimensional, Estimating true evolutionary distances between genomes, On optimal slicing of parallel programs, When is the evaluation of conjunctive queries tractable?, The complexity of maximal constraint languages, Quantitative solution of omega-regular games380872, Distribution functions of probabilistic automata, Compatible sequences and a slow Winkler percolation, Edge isoperimetry and rapid mixing on matroids and geometric Markov chains, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Computing with continuous-time Liapunov systems, Running time and program size for self-assembled squares, Algorithms, games, and the internet, Automata, circuits and hybrids, The Priority k-Median Problem, Segmentation, Incentives, and Privacy, Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model, Regular resolution lower bounds for the weak pigeonhole principle, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Clustering to minimize the sum of cluster diameters, Efficient algorithms for centers and medians in interval and circular-arc graphs, Fully-dynamic min-cut, Approximation algorithms for hard capacitated \(k\)-facility location problems, The price of selfish routing, An Improved Approximation Algorithm for Knapsack Median Using Sparsification, Improved algorithms for joint optimization of facility locations and network connections, An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation, Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties, An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee, Testing metric properties, Clustering to minimize the sum of cluster diameters, A new protocol and lower bounds for quantum coin flipping, Computing crossing numbers in quadratic time, Decidability of string graphs, Lower bounds for intersection searching and fractional cascading in higher dimension, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, LP-based approximation for uniform capacitated facility location problem, Grouping objects in multi-band images using an improved eigenvector-based algorithm, Convexified modularity maximization for degree-corrected stochastic block models, Local search approximation algorithms for the \(k\)-means problem with penalties, An approximation algorithm for soft capacitated \(k\)-facility location problem, Unnamed Item, The complexity of analytic tableaux, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Approximate distance oracles, Smoothed analysis of algorithms, A Streaming Algorithm for k-Means with Approximate Coreset, A \(k\)-product uncapacitated facility location problem, Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties, Ant colony optimization for finding medians of weighted graphs, An improved approximation algorithm for knapsack median using sparsification, Approximate solution of the \(p\)-median minimization problem, A factor graph model for unsupervised feature selection, Approximating min-sum k -clustering in metric spaces, Local search heuristic for k-median and facility location problems, Profit-earning facility location, One-dimensional quantum walks, Quantum walks on graphs, Quantum algorithms for solvable groups, Minimax parametric optimization problems and multi-dimensional parametric searching, Algorithms for minimizing weighted flow time, Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines, Stackelberg scheduling strategies, Quantum computers that can be simulated classically in polynomial time, Interaction in quantum communication and the complexity of set disjointness, Loss-less condensers, unbalanced expanders, and extractors, Spatial gossip and resource location protocols, (1 + εΒ) -spanner constructions for general graphs, Extractor codes, Excellent codes from modular curves, Sparse polynomial approximation in finite fields, Randomness efficient identity testing of multivariate polynomials, Euler paths in series parallel graphs, Learning mixtures of arbitrary gaussians, Learning DNF in time, Sampling algorithms, Testing of matrix properties, One line and ε, A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D, Sharp threshold and scaling window for the integer partitioning problem, A sharp threshold in proof complexity, Applications of approximation algorithms to cooperative games, Approximation algorithms for constrained for constrained node weighted steiner tree problems, A constant factor approximation for the single sink edge installation problems, Provisioning a virtual private network, Explicit lower bound of 4.5n - o(n) for boolena circuits, Lower bounds for matrix product, in bounded depth circuits with arbitrary gates, A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing, On the cell probe complexity of membership and perfect hashing, On the integrality ratio of semidefinite relaxations of MAX CUT, Non-approximability results for optimization problems on bounded degree instances, Colouring graphs when the number of colours is nearly the maximum degree, Data-streams and histograms, Optimal static range reporting in one dimension, Biased dictionaries with fast insert/deletes, Anti-persistence, Dynamic TCP acknowledgement and other stories about e/(e-1), Buffer overflow management in QoS switches, Almost optimal permutation routing on hypercubes, Online server allocation in a server farm via benefit task systems, Private approximation of NP-hard functions, Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, Black-box concurrent zero-knowledge requires \tilde {Ω} (log n ) rounds, The round complexity of verifiable secret sharing and secure multicast, Unnamed Item, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, Constant-Factor FPT Approximation for Capacitated k-Median, Network Cross-Validation for Determining the Number of Communities in Network Data, A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems, Reverse greedy is bad for \(k\)-center, Constant factor approximation algorithm for uniform hard capacitated knapsack median problem, Center-based clustering under perturbation stability, The ordered \(k\)-median problem: surrogate models and approximation algorithms, Agnostic Clustering, The reverse greedy algorithm for the metric k-median problem, Consistency of spectral clustering in stochastic block models, To close is easier than to open: dual parameterization to \(k\)-median