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.

Short Bio: David S. Johnson is Head of the Algorithms and Optimization Department at AT&T Labs-Research in Florham Park, NJ, and has been a researcher at the Labs (in its many incarnations) since 1973, when he received his Ph.D from MIT. The author of over 100 technical papers, he is perhaps best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which he shared the Lanchester Prize of the Operations Research Society of America (1979). His research interests (in addition to the theory of NP-completeness) include approximation algorithms for combinatorial problems, and the experimental analysis of algorithms, with special emphasis on bin packing, graph coloring, and the traveling salesman problem. As one of the founders of ACM's Kanellakis Prize, he is particularly interested in recognizing and encouraging the interaction between theory and practice in computer science.