[Colloquium] TTI-C Colloquium: Konstantin Makarychev, IBM

[Julia MacGlashan]

When:             Monday, Oct 5 @ 1:00pm

Where:            TTI-C Conference Room #526, 6045 S Kenwood Ave, 5th Floor

Who:               Konstantin Makarychev (IBM T.J. Watson Research Center)

Title:                Sparse Rectangular Representations of Matrix Data


Given a matrix of integers, how compactly can we exactly represent the
matrix as a sum of weighted rectangles?  More precisely, given a set of
allowable rectangles, using a linear combination of how few allowed
rectangles can we represent the matrix?

We study two variants.  Motivated by database applications, the first case
allows rectangles given by the cross product of two trees. Specifically, we
are given one tree whose leaves are the rows and another whose leaves are
the columns.  A rectangle is allowed if and only if it is the cross product
between the leaf descendants of a node in the first tree and the leaf
descendants of a node in the second tree. The second variant of the problem
allows all rectangles.

For the database application, we give a 2-approximation algorithm and prove
the problem NP-hard. We give a 2.56-approximation algorithm for second
variant of the problem and prove it NP-Hard. To our knowledge these are the
first results for the problem of sparsely and exactly representing matrices
by weighted rectangles.

Joint work with Howard Karloff, Flip Korn, and Yuval Rabani.

Contact:          Yury Makarychev, yury at tti-c.org

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090930/1fb62338/attachment.htm