Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-8726
Main Title: Co-Clustering under the Maximum Norm
Author(s): Bulteau, Laurent
Froese, Vincent
Hartung, Sepp
Niedermeier, Rolf
Type: Article
Language Code: en
Abstract: Co-clustering, that is partitioning a numerical matrix into “homogeneous” submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from {0, 1, 2}.
URI: https://depositonce.tu-berlin.de/handle/11303/9686
http://dx.doi.org/10.14279/depositonce-8726
Issue Date: 25-Feb-2016
Date Available: 1-Aug-2019
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): bi-clustering
matrix partitioning
NP-hardness
SAT solving
fixed-parameter tractability
Sponsor/Funder: DFG, 218550609, Datenreduktion in der parametrisierten Algorithmik: neue Modelle und Methoden (DAMM)
License: https://creativecommons.org/licenses/by/4.0/
Journal Title: Algorithms
Publisher: MDPI
Publisher Place: Basel
Volume: 9
Issue: 1
Article Number: 17
Publisher DOI: 10.3390/a9010017
EISSN: 1999-4893
Appears in Collections:FG Algorithmik und Komplexitätstheorie » Publications

Files in This Item:
File Description SizeFormat 
algorithms-09-00017.pdf352.66 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons