Seminars & Colloquia
AT & T Research Labs
"Compressing Rectilinear Pictures, with Applications to Internet Routing"
Monday November 14, 2005 04:00 PM
Location: 313, MRC NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Triangle Computer Science Distinguished Lecturer Series
Here the goal is to create a colored rectilinear pattern within an initially white square canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Motivated by the ACL application, we study the special case in which all rectangles must be strips that extend either the full length or the full height of the canvas. We provide several equivalent characterizations of the patterns achievable in this special case and present a polynomial-time algorithm for optimally constructing such patterns when, as in the ACL application, the only colors are black and white (permit or deny). We also bound the improvement one can obtain by using arbitrary rectangles in the construction of such patterns, and analyze heuristics for the case of general patterns.
This is joint work with David Applegate, Gruia Calinescu, Howard Karloff, Katrina Ligett, and Jia Wang.
Host: Matt Stallmann and Franc Brglez, Computer Science, NCSU