Sie sind hier

The Complexity of Co-Clustering Under the Maximum Norm

Vincent Froese (TU Berlin)

Co-clustering, that is, partitioning a matrix into homogeneous submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants in the literature 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. This problem turns out to be intractable even for some very restricted cases.
We spot several NP-hard as well as some polynomial-time solvable special cases. We also indicate some fixed-parameter tractable cases.

Joint work with Laurent Bulteau, Sepp Hartung and Rolf Niedermeier.

Date
Speaker
Location
Language
12.06.2014 16:15
Vincent Froese
TEL 512
english