Parameterized \(k\)-clustering: tractability island

DOI10.1016/j.jcss.2020.10.005zbMath1477.68132OpenAlexW3100384259MaRDI QIDQ2221803

Fedor V. Fomin, Kirill Simonov, Petr A. Golovach

Publication date: 2 February 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2020.10.005

zbMATH Keywords

clusteringparameterized complexity\(k\)-means\(k\)-median

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Parameterized complexity of categorical clustering with size constraints ⋮ Parameterized complexity of categorical clustering with size constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• NP-hardness of Euclidean sum-of-squares clustering
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Which problems have strongly exponential complexity?
• Co-clustering under the maximum norm
• Clustering for metric and nonmetric distance measures
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Approximating extent measures of points
• On the Complexity of Some Common Geometric Location Problems
• Closest Substring Problems with Small Distances
• Consensus Patterns (Probably) Has no EPTAS
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• The Planar k-Means Problem is NP-Hard
• Color-coding
• Least squares quantization in PCM
• Parameterized Low-Rank Binary Matrix Approximation
• A unified framework for approximating and clustering data
• Parameterized Algorithms
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

This page was built for publication: Parameterized \(k\)-clustering: tractability island