Compressing rectilinear pictures and minimizing access control lists
Compressing rectilinear pictures and minimizing access control lists
复制标题
DOI：
--
复制
发表时间：
2007-01
期刊：
影响因子：
--
通讯作者：
David L. Applegate;G. Călinescu;David S. Johnson;H. Karloff;Katrina Ligett;Jia Wang
中科院分区：
文献类型：
--
作者：
David L. Applegate;G. Călinescu;David S. Johnson;H. Karloff;Katrina Ligett;Jia Wang
我们考虑了网络路由器中访问控制列表（acl）最小化问题的几何模型，该模型也适用于普通图形软件包中的直线图像压缩和图形绘制。这里的目标是在最初的白色矩形画布中创建一个彩色的直线图案，基本操作是选择一个子矩形并将其涂成单一颜色，覆盖矩形中先前的所有颜色。矩形规则列表最小化是找到创建给定模式所需的最短规则列表的问题。ACL最小化是该问题的限制版本，其中允许的矩形集合必须对应于IP地址前缀对。在ACL应用程序的激励下，我们研究了RRL和ACL最小化的特殊情况，其中所有矩形必须是扩展画布的全宽或全高的条带（条带规则）。我们提供了使用条带规则可实现的模式的几个等效特征，并提供了多项式时间算法，用于在ACL应用程序中，只有黑色和白色（允许或拒绝）时最优地构建这种模式。我们还证明了RRL最小化通常是np困难的，并通过利用我们关于条形规则模式的结果，为一般RRL和ACL最小化提供了O（min(n1/3, OPT1/2)）个近似算法。
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(n1/3, OPT1/2))-approximation algorithms for general RRL and ACL minimization by exploiting our results about strip-rule patterns.