scientific article; zbMATH DE number 7561535
From MaRDI portal
Publication:5091192
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 1.488 approximation algorithm for the uncapacitated facility location problem
- A birthday repetition theorem and complexity of approximating dense CSPs
- A constant-factor approximation algorithm for the k-median problem
- A local search approximation algorithm for \(k\)-means clustering
- A Parallel Repetition Theorem
- A threshold of ln n for approximating set cover
- A unified framework for approximating and clustering data
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Approximating k-median via pseudo-approximation
- Facility Location with Matroid or Knapsack Constraints
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved and simplified inapproximability for \(k\)-means
- Improved approximation algorithms for matroid and knapsack median problems and applications
- Linear-time approximation schemes for clustering problems in any dimensions
- Maximizing a monotone submodular function subject to a matroid constraint
- On k-Median clustering in high dimensions
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- On the parameterized complexity of approximating dominating set
- Small space representations for metric min-sum k-clustering and their applications
- The hardness of approximation of Euclidean k-means
- The parameterized complexity of k-biclique
- Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering
Cited in
(41)- Lossy kernelization of same-size clustering
- On parameterized approximation algorithms for balanced clustering
- To close is easier than to open: dual parameterization to \(k\)-median
- Improved parameterized approximation for balanced \(k\)-median
- On the fixed-parameter tractability of capacitated clustering
- A unified framework of FPT approximation algorithms for clustering problems
- Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
- FPT Approximation for Constrained Metric k-Median/Means
- New algorithms for fair \(k\)-center problem with outliers and capacity constraints
- Tight FPT approximation for socially fair clustering
- Approximation schemes for k-facility location
- Lossy kernelization of same-size clustering
- A PTAS framework for clustering problems in doubling metrics
- k-median/means with outliers revisited: a simple fpt approximation
- Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
- 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
- Clustering under perturbation stability in near-linear time
- Parameterized inapproximability for Steiner orientation by gap amplification
- Baby PIH: Parameterized inapproximability of min CSP
- Hybrid k-clustering: blending k-median and k-center
- Satisfiability to coverage in presence of fairness, matroid, and global constraints
- Parameterized approximation for robust clustering in discrete geometric spaces
- Parameterized inapproximability hypothesis under ETH
- Improved approximation algorithm for individual fairness k-median
- On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
- Hybrid k-clustering: blending k-median and k-center
- Clustering under a knapsack constraint: parameterized approximation for the knapsack median problem
- Polynomial-time approximation schemes for facility location on planar graphs
- Clustering what matters in constrained settings (improved outlier to outlier-free reductions)
- Clustering what matters in constrained settings: improved outlier to outlier-free reductions
- Untangling Gaussian mixtures
- Clustering with a knapsack constraint: parameterized approximation algorithms for the knapsack median problem
- Separating \(k\)-\textsc{Median} from the supplier version
- Achieving anonymity via weak lower bound constraints for k-median and k-means
- On the budgeted priority p-median problem in high-dimensional Euclidean spaces
- Better guarantees for individual fairness k-median
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- On equivalence of parameterized inapproximability of \(k\)-median, \(k\)-max-coverage, and 2-CSP
- FPT approximations for fair k-min-sum-radii
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)
