Co-Clustering under the Maximum Norm
dc.contributor.author | Bulteau, Laurent | |
dc.contributor.author | Froese, Vincent | |
dc.contributor.author | Hartung, Sepp | |
dc.contributor.author | Niedermeier, Rolf | |
dc.date.accessioned | 2019-08-01T14:31:11Z | |
dc.date.available | 2019-08-01T14:31:11Z | |
dc.date.issued | 2016-02-25 | |
dc.date.updated | 2019-07-23T13:05:23Z | |
dc.description.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}. | en |
dc.description.sponsorship | DFG, 218550609, Datenreduktion in der parametrisierten Algorithmik: neue Modelle und Methoden (DAMM) | en |
dc.identifier.eissn | 1999-4893 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/9686 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-8726 | |
dc.language.iso | en | en |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | en |
dc.subject.ddc | 004 Datenverarbeitung; Informatik | de |
dc.subject.other | bi-clustering | en |
dc.subject.other | matrix partitioning | en |
dc.subject.other | NP-hardness | en |
dc.subject.other | SAT solving | en |
dc.subject.other | fixed-parameter tractability | en |
dc.title | Co-Clustering under the Maximum Norm | en |
dc.type | Article | en |
dc.type.version | publishedVersion | en |
dcterms.bibliographicCitation.articlenumber | 17 | en |
dcterms.bibliographicCitation.doi | 10.3390/a9010017 | en |
dcterms.bibliographicCitation.issue | 1 | en |
dcterms.bibliographicCitation.journaltitle | Algorithms | en |
dcterms.bibliographicCitation.originalpublishername | MDPI | en |
dcterms.bibliographicCitation.originalpublisherplace | Basel | en |
dcterms.bibliographicCitation.volume | 9 | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Algorithmik und Komplexitätstheorie | de |
tub.affiliation.faculty | Fak. 4 Elektrotechnik und Informatik | de |
tub.affiliation.group | FG Algorithmik und Komplexitätstheorie | de |
tub.affiliation.institute | Inst. Softwaretechnik und Theoretische Informatik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |