On the parameterized complexity of clustering problems for incomplete data

DOI10.1016/J.JCSS.2022.12.001MaRDI QIDQ2689366zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Robert Ganian, Sebastian Ordyniak, Stefan Szeider, Iyad Kanj

Publication date 10 March 2023

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

Full work available at URL https://arxiv.org/abs/1911.01465

zbMATH Keywords

clusteringincomplete dataparameterized complexity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational aspects of data analysis and big data (68T09) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Clustering affine subspaces: hardness and algorithms
• Parameterized \(k\)-clustering: tractability island
• Clustering with Partial Information
• Clustering with partial information

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305511 (Why is no real title available?)
• scientific article; zbMATH DE number 7525465 (Why is no real title available?)
• scientific article; zbMATH DE number 2205355 (Why is no real title available?)
• A simple heuristic for the p-centre problem
• Approximation Schemes for Low-rank Binary Matrix Approximation Problems
• Approximation algorithms for Hamming clustering problems
• Clustering to minimize the maximum intercluster distance
• Clustering to minimize the sum of cluster diameters
• Combinatorial Pattern Matching
• Data Clustering: Theory, Algorithms, and Applications
• Exact matrix completion via convex optimization
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Fundamentals of parameterized complexity
• Geometric clustering, fixed-parameter tractability and lower bounds with respect to the dimension
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• Intersection Theorems for Systems of Sets
• Kernelization. Theory of parameterized preprocessing
• On covering problems of codes
• Parameterized Algorithms for Matrix Completion with Radius Constraints.
• Parameterized algorithms
• Parameterized complexity analysis for the closest string with wildcards problem
• Parameterized complexity and kernelizability of max ones and exact ones problems
• Parameterized complexity of constraint satisfaction problems
• Parameterized k-Clustering: Tractability Island
• Parameterized low-rank binary matrix approximation
• Parametrized complexity theory.
• Partition into triangles on bounded degree graphs
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

Cited in

(1)

• Parameterized Complexity of Feature Selection for Categorical Data Clustering.

This page was built for publication: On the parameterized complexity of clustering problems for incomplete data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2689366)