Approximating k-median via pseudo-approximation
From MaRDI portal
Publication:5495862
DOI10.1145/2488608.2488723zbMath1293.90061OpenAlexW2165420145MaRDI QIDQ5495862
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488723
Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (28)
Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median ⋮ An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ 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 ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ Discrete facility location in machine learning ⋮ Universal Algorithms for Clustering Problems ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Recovery guarantees for exemplar-based clustering ⋮ An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An approximation algorithm for soft capacitated \(k\)-facility location problem ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ An improved approximation algorithm for knapsack median using sparsification ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ 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 Lottery Model for Center-Type Problems With Outliers ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Consistency of spectral clustering in stochastic block models
This page was built for publication: Approximating k-median via pseudo-approximation
