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