On the parameterized complexity of clustering problems for incomplete data

DOI10.1016/J.JCSS.2022.12.001OpenAlexW4313406961MaRDI QIDQ2689366FDOQ2689366

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

Recommendations

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

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)

Cites Work

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

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)