scientific article; zbMATH DE number 7561535
From MaRDI portal
Publication:5091192
DOI10.4230/LIPICS.ICALP.2019.42MaRDI QIDQ5091192FDOQ5091192
Authors: Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li 
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1904.12334
Title of this publication is not available (Why is that?)
Recommendations
- FPT Approximation for Constrained Metric k-Median/Means
- Approximating \(k\)-median via pseudo-approximation
- Approximating k-median via pseudo-approximation
- scientific article; zbMATH DE number 1775394
- Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
- Approximation Algorithms for the k-Median Problem
- Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
- scientific article; zbMATH DE number 2090269
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- Approximating \(k\)-median with non-uniform capacities
Cites Work
- A threshold of ln n for approximating set cover
- Turning big data into tiny data: constant-size coresets for \(k\)-means, PCA and projective clustering
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- Greedy Strikes Back: Improved Facility Location Algorithms
- The parameterized complexity of \(k\)-biclique
- Maximizing a monotone submodular function subject to a matroid constraint
- A Parallel Repetition Theorem
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Approximating \(k\)-median via pseudo-approximation
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- Linear-time approximation schemes for clustering problems in any dimensions
- On k-Median clustering in high dimensions
- The hardness of approximation of Euclidean \(k\)-means
- A constant-factor approximation algorithm for the \(k\)-median problem
- On the parameterized complexity of approximating dominating set
- A local search approximation algorithm for \(k\)-means clustering
- A unified framework for approximating and clustering data
- Improved and simplified inapproximability for \(k\)-means
- Facility Location with Matroid or Knapsack Constraints
- Small space representations for metric min-sum \(k\)-clustering and their applications
- A birthday repetition theorem and complexity of approximating dense CSPs
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Improved approximation algorithms for matroid and knapsack median problems and applications
Cited In (18)
- On parameterized approximation algorithms for balanced clustering
- To close is easier than to open: dual parameterization to \(k\)-median
- A PTAS framework for clustering problems in doubling metrics
- \(k\)-median/means with outliers revisited: a simple fpt approximation
- A unified framework of FPT approximation algorithms for clustering problems
- Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
- Tight FPT approximation for socially fair clustering
- FPT Approximation for Constrained Metric k-Median/Means
- Improved parameterized approximation for balanced \(k\)-median
- Approximation schemes for \(k\)-facility location
- Title not available (Why is that?)
- FPT approximation for capacitated clustering with outliers
- Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
- Approximation schemes for Min-Sum \(k\)-Clustering
- Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
- Lossy kernelization of same-size clustering
- Lossy kernelization of same-size clustering
- New algorithms for fair \(k\)-center problem with outliers and capacity constraints
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091192)
