Speaker: David Johnson, AT&T Labs - Research
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Compressing Rectilinear Pictures, with Applications to the Internet
Abstract:
We consider a geometric model for the problem of minimizing access control
lists (ACLs) in network routers. This model is a generalization of
one previously studied in the context of rectilinear picture compression.
It embodies an optimization problem that arises when drawing figures
using common software packages such as Excel and Xfig.
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.