NP-hardness of Euclidean sum-of-squares clustering
From MaRDI portal
Publication:1009338
DOI10.1007/s10994-009-5103-0zbMath1378.68047OpenAlexW2086959852WikidataQ56500747 ScholiaQ56500747MaRDI QIDQ1009338
Amit Deshpande, Preyas Popat, Daniel Aloise, Pierre Hansen
Publication date: 31 March 2009
Published in: Machine Learning (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10994-009-5103-0
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Modeling time-dependent randomness in stochastic dual dynamic programming, Iterative algorithm for discrete structure recovery, Network bipartitioning in the anti-communicability Euclidean space, Exact algorithms for size constrained 2-clustering in the plane, Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem, On the complexity of some quadratic Euclidean 2-clustering problems, Clustering cities based on their development dynamics and variable neigborhood search, Information-theoretic feature selection with discrete \(k\)-median clustering, An improved approximation algorithm for squared metric \(k\)-facility location, An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors, A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem, A survey on feature weighting based K-means algorithms, Demand point aggregation method for covering problems with gradual coverage, Soft clustering by convex electoral model, Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters, Flow-based dissimilarity measures for reservoir models: a spatial-temporal tensor approach, An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space, On strategies to fix degenerate \(k\)-means solutions, Compressive statistical learning with random feature moments, Statistical learning guarantees for compressive clustering and compressive mixture modeling, Visual attractiveness in vehicle routing via bi-objective optimization, Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering, New heuristic for harmonic means clustering, A bad instance for \texttt{k-means++}, An exact algorithm for semi-supervised minimum sum-of-squares clustering, Structural conditions for projection-cost preservation via randomized matrix multiplication, Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering, Local search approximation algorithms for the \(k\)-means problem with penalties, On the complexity of redescription mining, NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes, On the complexity of some problems of searching for a family of disjoint clusters, Recovery guarantees for exemplar-based clustering, Improved PTAS for the constrained \(k\)-means problem, New and efficient DCA based algorithms for minimum sum-of-squares clustering, Exact pseudopolynomial algorithms for a balanced 2-clustering problem, Global optimality in \(k\)-means clustering, An LP-based \(k\)-means algorithm for balancing weighted point sets, Balanced \(k\)-means clustering on an adiabatic quantum computer, On the complexity of piecewise affine system identification, Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering, NP-hardness of some quadratic Euclidean 2-clustering problems, Mathematical Programming Formulations and Algorithms for Discrete k-Median Clustering of Time-Series Data, Particle swarm optimization with age-group topology for multimodal functions and data clustering, Variable neighborhood search for harmonic means clustering, On the complexity of clustering with relaxed size constraints in fixed dimension, Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters, The planar \(k\)-means problem is NP-hard, The complexity of finding uniform sparsest cuts in various graph classes, Size matters: choosing the most informative set of window lengths for mining patterns in event sequences, Optimising sum-of-squares measures for clustering multisets defined over a metric space, \(k\)-means genetic algorithms with greedy genetic operators, A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets, Guaranteed clustering and biclustering via semidefinite programming, A constant FPT approximation algorithm for hard-capacitated \(k\)-means, Approximation algorithms for spherical \(k\)-means problem using local search scheme, Parameterized \(k\)-clustering: tractability island, An improved column generation algorithm for minimum sum-of-squares clustering, The Complexity Status of Problems Related to Sparsest Cuts, Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering, An approximation polynomial-time algorithm for a sequence bi-clustering problem, Graph summarization with quality guarantees, A Bad Instance for k-Means++, Improved and simplified inapproximability for \(k\)-means, An efficient \(K\)-means clustering algorithm for tall data, Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center, An iterated greedy heuristic for a market segmentation problem with multiple attributes, J-means and I-means for minimum sum-of-squares clustering on networks, Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems, Cross-entropy clustering, Temporally consistent tone mapping of images and video using optimal \(K\)-means clustering, Dense and sparse graph partition, On polynomial solvability of one quadratic Euclidean clustering problem on a line, The Planar k-Means Problem is NP-Hard, A dual reformulation and solution framework for regularized convex clustering problems, Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem, Robust K-Median and K-means clustering algorithms for incomplete data, When do birds of a feather flock together? \(k\)-means, proximity, and conic programming, The seeding algorithm for \(k\)-means problem with penalties, Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability, Convex programming based spectral clustering, Real-Time Valuation of Large Variable Annuity Portfolios: A Green Mesh Approach, A memetic algorithm based on reformulation local search for minimum sum-of-squares clustering in networks, NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters, Fast and efficient nested simulation for large variable annuity portfolios: a surrogate modeling approach, The seeding algorithms for spherical \(k\)-means clustering, On the Complexity of Clustering with Relaxed Size Constraints, A Lagrangian-based score for assessing the quality of pairwise constraints in semi-supervised clustering, The approximation algorithm based on seeding method for functional \(k\)-means problem, Degeneracy on K-means clustering, Boosting isomorphic model filtering with invariants, The bi-criteria seeding algorithms for two variants of \(k\)-means problem, An approximation algorithm for the uniform capacitated \(k\)-means problem, The seeding algorithm for spherical \(k\)-means clustering with penalties, Approximation algorithm for spherical \(k\)-means problem with penalty, A fast k-prototypes algorithm using partial distance computation, Consistency of spectral clustering in stochastic block models, A randomized algorithm for two-cluster partition of a set of vectors, Variable neighborhood search for minimum sum-of-squares clustering on networks, K-means clustering via a nonconvex optimization approach, Scenario reduction revisited: fundamental limits and guarantees, A comparative analysis of granular computing clustering from the view of set, k-POD: A Method for k-Means Clustering of Missing Data, Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems, An improved primal-dual approximation algorithm for the k-means problem with penalties, Local Versions of Sum-of-Norms Clustering, Improved Conic Reformulations for $K$-means Clustering, Unnamed Item, Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space, Discrete facility location in machine learning, One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering, An explainable autoencoder with multi-paradigm fMRI fusion for identifying differences in dynamic functional connectivity during brain development, Effective Heuristic Techniques for Combined Robust Clustering Problem, Latent group detection in functional partially linear regression models, Clustering with faulty centers, The provably good parallel seeding algorithms for the k‐means problem with penalties, SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering, Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces, K‐Plus anticlustering: An improved k‐means criterion for maximizing between‐group similarity, Semi-supervised \(k\)-means clustering via DC programming approach, Constant-factor approximation algorithms for some maximin multi-clustering problems, PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem, Also for \(k\)-means: more data does not imply better performance, How to find a good explanation for clustering?, Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space, Mixed-integer programming techniques for the minimum sum-of-squares clustering problem, Qualitative properties of the minimum sum-of-squares clustering problem, Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case, Information-Maximization Clustering Based on Squared-Loss Mutual Information, EFFICIENT DYNAMIC HEDGING FOR LARGE VARIABLE ANNUITY PORTFOLIOS WITH MULTIPLE UNDERLYING ASSETS, Local Search Yields a PTAS for $k$-Means in Doubling Metrics, Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization, Non-convex clustering via proximal alternating linearized minimization method, Noisy, Greedy and Not so Greedy k-Means++, The Parallel Seeding Algorithm for k-Means Problem with Penalties, Unnamed Item, FPT Approximation for Constrained Metric k-Median/Means, On the Role of Homogeneity When Controlling Single‐Leader Networks, Unnamed Item, Easy NP-hardness Proofs of Some Subset Choice Problems, The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension, Good Clusterings Have Large Volume, Scenario Grouping and Decomposition Algorithms for Chance-Constrained Programs, A Performance Guarantee for Spectral Clustering, Unnamed Item, An FPTAS for a vector subset search problem, Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
Uses Software
Cites Work
