Linear-time approximation schemes for clustering problems in any dimensions
From MaRDI portal
Recommendations
- Automata, Languages and Programming
- Approximation schemes for clustering problems
- Near-linear Time Approximation Schemes for Clustering in Doubling Metrics
- Exact and approximation algorithms for clustering
- Optimal time bounds for approximate clustering
- Sublinear time approximate clustering
- scientific article; zbMATH DE number 1303609
- scientific article; zbMATH DE number 1629976
- A linear time algorithm for approximate 2-means clustering
- An approximation algorithm for a problem of cluster analysis
Cited in
(83)- Lossy kernelization of same-size clustering
- Sublinear‐time approximation algorithms for clustering via random sampling
- A unified framework for clustering constrained data without locality property
- Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
- Clustering what matters in constrained settings: improved outlier to outlier-free reductions
- On ultrametric 1-median selection
- A linear time algorithm for approximate 2-means clustering
- Near-linear Time Approximation Schemes for Clustering in Doubling Metrics
- On the fixed-parameter tractability of capacitated clustering
- Approximation and complexity of the capacitated geometric median problem
- A linear-time approximation algorithm for the minimum-length geometric embedding of trees
- A fast approximation scheme for low-dimensional k-means
- scientific article; zbMATH DE number 7053357 (Why is no real title available?)
- Deterministic metric 1-median selection with A 1-o(1) fraction of points ignored
- Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
- Clustering with a knapsack constraint: parameterized approximation algorithms for the knapsack median problem
- Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1]
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- Linear-size universal discretization of geometric center-based problems in fixed dimensions
- An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Probabilistic k-median clustering in data streams
- Net and prune: a linear time algorithm for Euclidean distance problems
- Parameterized approximation algorithms and lower bounds for k-center clustering and variants
- Deterministic metric 1-median selection with very few queries
- Net and prune: a linear time algorithm for Euclidean distance problems
- A unified framework of FPT approximation algorithms for clustering problems
- Subquadratic approximation algorithms for clustering problems in high dimensional spaces
- Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space
- Local search yields a PTAS for \(k\)-means in doubling metrics
- Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
- On variants of k-means clustering
- Subquadratic approximation algorithms for clustering problems in high dimensional spaces
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- Parameterized low-rank binary matrix approximation
- Parameterized \(k\)-clustering: tractability island
- Approximation schemes for clustering problems
- Interactive clustering of linear classes and cryptographic lower bounds
- Faster balanced clusterings in high dimension
- Faster algorithms for the constrained k-means problem
- Approximate Clustering with Same-Cluster Queries
- Data stability in clustering: a closer look
- On the budgeted priority p-median problem in high-dimensional Euclidean spaces
- Almost optimal solutions to k-clustering problems
- FPT Approximation for Constrained Metric k-Median/Means
- On sampling based algorithms for k-means
- Faster approximation schemes for (constrained) k-means with outliers
- Universal Algorithms for Clustering Problems
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- Automata, Languages and Programming
- Polynomial-time approximation schemes for geometric min-sum median clustering
- Improved analysis of D^2-sampling based PTAS for k-means and other clustering problems
- How to find a good explanation for clustering?
- A lower bound for metric 1-median selection
- On connections between k-coloring and Euclidean k-means
- Coresets for k-median of lines with group fairness constraints
- Some results on approximate 1-median selection in metric spaces
- Efficient approximation schemes for uniform-cost clustering problems in planar graphs
- Bi-criteria linear-time approximations for generalized k-mean/median/center
- A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection
- Hybrid k-clustering: blending k-median and k-center
- Clustering through continuous facility location problems
- Parameterized approximation for robust clustering in discrete geometric spaces
- On clustering bodies: geometry and polyhedral approximation
- Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
- Improved PTAS for the constrained \(k\)-means problem
- Automata, Languages and Programming
- Parameterized low-rank binary matrix approximation
- Turning big data into tiny data: coresets for unsupervised learning problems
- An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions
- Linear-time approximation scheme for k-means clustering of axis-parallel affine subspaces
- Efficient coreset construction algorithm for fair k-median of lines
- Learning the truth vector in high dimensions
- Clustering lines in high-dimensional space, classification of incomplete data
- Clustering with internal connectedness
- Hybrid k-clustering: blending k-median and k-center
- Polynomial-time approximation schemes for facility location on planar graphs
- On Las Vegas approximations for metric 1-median selection
- scientific article; zbMATH DE number 7164768 (Why is no real title available?)
- Clustering what matters in constrained settings (improved outlier to outlier-free reductions)
- Metric 1-median selection: query complexity vs. approximation ratio
- Better guarantees for \(k\)-median with service installation costs
- Lossy kernelization of same-size clustering
This page was built for publication: Linear-time approximation schemes for clustering problems in any dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3578186)
