On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data

Howard Karloff, Flip Korn, Konstantin Makarychev & Yuval Rabani
This paper studies the ``explanation problem'' for tree- and linearly-ordered array data, a problem motivated by database applications and recently solved for the one-dimensional tree-ordered case. In this paper, one is given a matrix A=(a_{ij}) whose rows and columns have semantics: special subsets of the rows and special subsets of the columns are meaningful, others are not. A submatrix in A is said to be meaningful if and only if it is the cross product...