A Caltech Library Service

Compressing rectilinear pictures and minimizing access control lists

Applegate, David A. and Calinescu, Gruia and Johnson, David S. and Karloff, Howard and Ligett, Katrina and Wang, Jia (2007) Compressing rectilinear pictures and minimizing access control lists. In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, pp. 1066-1075. ISBN 978-0-898716-24-5.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in common graphics software packages. Here the goal is to create a colored rectilinear pattern within an initially white rectangular canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Rectangle Rule List (RRL) minimization is the problem of finding the shortest list of rules needed to create a given pattern. ACL minimization is a restricted version of this problem where the set of allowed rectangles must correspond to pairs of IP address prefixes. Motivated by the ACL application, we study the special cases of RRL and ACL minimization in which all rectangles must be strips that extend either the full width or the full height of the canvas (strip-rules). We provide several equivalent characterizations of the patterns achievable using strip-rules and present polynomial-time algorithms for optimally constructing such patterns when, as in the ACL application, the only colors are black and white (permit or deny). We also show that RRL minimization is NP-hard in general and provide O(min(n^(1/3), OPT^(1/2)))-approximation algorithms for general RRL and ACL minimization by exploiting our results about strip-rule patterns.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Ligett, Katrina0000-0003-2780-6656
Additional Information:© 2007 Society for Industrial and Applied Mathematics.
Record Number:CaltechAUTHORS:20190110-140236006
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92203
Deposited By: Tony Diaz
Deposited On:11 Jan 2019 05:05
Last Modified:03 Oct 2019 20:42

Repository Staff Only: item control page