March 12, 2008
Howard Karloff
AT&T Labs, Inc., Florham Park, NJ
Title: PAINTING RECTILINEAR PICTURES WITHOUT PICASSO
Abstract: I will talk about the following fun 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 the world of art, this problem has application to cubism (c.f. Picasso, Braque, Cezanne). In computer science 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 algorithms for the NP-Complete general case.
This is joint work with David A. Applegate, Gruia Calinescu, David S. Johnson, Katrina Ligett, and Jia Wang.