Abstract:

I will talk about the following semi-artistic question:  Given a
rectilinear blue-and-white target pattern, how many steps does it take
to "paint" the rectilinear pattern, starting from an all-white canvas,
if in each step one chooses a rectangle and paints it blue
or white, overwriting any previous colors?
In art world, this problem has application to cubism
(c.f. Picasso, Braque, Cezanne).  In the computer science world, this 
problem has application to minimizing "access control lists" which 
are used by routers to decide whether to forward or drop an incoming packet.

I will show how, for a useful special case, one can get the exact
optimum in polynomial time, and I will discuss an approximation algorithm
for the NP-Complete general case.

This is joint work with David A. Applegate, Gruia Calinescu, 
David S. Johnson, Katrina Ligett, and Jia Wang.