## Abstract

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 of a meaningful row subset and a meaningful column subset, in which case we call it an "allowed rectangle." The goal is to "explain" A as a sparse sum of weighted allowed rectangles. Specifically, we wish to find as few weighted allowed rectangles as possible such that, for all i, j, a_{ij} equals the sum of the weights of all rectangles which include cell (i, j). In this paper we consider the natural cases in which the matrix dimensions are tree-ordered or linearly-ordered. In the tree-ordered case, we are given a rooted tree T_{1} whose leaves are the rows of A and another, T_{2}, whose leaves are the columns. Nodes of the trees correspond in an obvious way to the sets of their leaf descendants. In the linearly-ordered case, a set of rows or columns is meaningful if and only if it is contiguous. For tree-ordered data, we prove the explanation problem NP-Hard and give a randomized 2-approximation algorithm for it. For linearly-ordered data, we prove the explanation problem NP-Hard and give a 2.56-approximation algorithm. To our knowledge, these are the first results for the problem of sparsely and exactly representing matrices by weighted rectangles.

Original language | English (US) |
---|---|

Title of host publication | 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 |

Pages | 332-343 |

Number of pages | 12 |

Volume | 9 |

DOIs | |

State | Published - Dec 1 2011 |

Event | 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 - Dortmund, Germany Duration: Mar 10 2011 → Mar 12 2011 |

### Other

Other | 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 |
---|---|

Country | Germany |

City | Dortmund |

Period | 3/10/11 → 3/12/11 |

## ASJC Scopus subject areas

- Software