Co-Clustering under the Maximum Norm

dc.contributor.authorBulteau, Laurent
dc.contributor.authorFroese, Vincent
dc.contributor.authorHartung, Sepp
dc.contributor.authorNiedermeier, Rolf
dc.date.accessioned2019-08-01T14:31:11Z
dc.date.available2019-08-01T14:31:11Z
dc.date.issued2016-02-25
dc.date.updated2019-07-23T13:05:23Z
dc.description.abstractCo-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.sponsorshipDFG, 218550609, Datenreduktion in der parametrisierten Algorithmik: neue Modelle und Methoden (DAMM)en
dc.identifier.eissn1999-4893
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/9686
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-8726
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc004 Datenverarbeitung; Informatikde
dc.subject.otherbi-clusteringen
dc.subject.othermatrix partitioningen
dc.subject.otherNP-hardnessen
dc.subject.otherSAT solvingen
dc.subject.otherfixed-parameter tractabilityen
dc.titleCo-Clustering under the Maximum Normen
dc.typeArticleen
dc.type.versionpublishedVersionen
dcterms.bibliographicCitation.articlenumber17en
dcterms.bibliographicCitation.doi10.3390/a9010017en
dcterms.bibliographicCitation.issue1en
dcterms.bibliographicCitation.journaltitleAlgorithmsen
dcterms.bibliographicCitation.originalpublishernameMDPIen
dcterms.bibliographicCitation.originalpublisherplaceBaselen
dcterms.bibliographicCitation.volume9en
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Algorithmik und Komplexitätstheoriede
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.groupFG Algorithmik und Komplexitätstheoriede
tub.affiliation.instituteInst. Softwaretechnik und Theoretische Informatikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
algorithms-09-00017.pdf
Size:
352.66 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.9 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections