二维子阵多面体在直线图片压缩问题中的应用及理论研究

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）557-566www.elsevier.com/locate/entcs二维子阵多面体Ivo Kocha，1 Javier Marencob，2a阿根廷萨米恩托国立大学工业学院b阿根廷萨米恩托国立大学科学研究所摘要给定一个d维数组，最大子数组问题在于找到数组的轴平行切片，使其条目之和最大化。在这项工作中，我们开始一个多面体的研究自然整数规划制定这个问题时，d= 2。这种探索的动机是需要解决大规模的实例的直线图片压缩问题（RPC），出现在不同的情况下的问题所得到的结果可以是有用的，以解决列生成阶段的一个分支和价格的方法RPC，一种技术，自然适用于这个问题。因此，我们定义了2D子阵列多面体，探索确保线性不等式有效性的条件，并提供了几个家庭的小平面诱导不等式。保留字：最大子阵问题，整数规划，刻面1介绍直线图像压缩问题（RPC）是用最少数量的具有连续行和连续列的子矩阵（以下称为矩形）覆盖二进制矩阵M∈ {0， 1}m×n的所有值为1的使得每个矩形仅包含M中值为1的条目。虽然探索RPC的最初动机来自于单色图像的压缩（特别是来自矩形构造的图像），但该问题也适用于其他场景。1电子邮件：ikoch@ungs.edu.ar2电子邮件：jmarenco@ungs.edu.arhttps://doi.org/10.1016/j.entcs.2019.08.0491571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。558I. Koch，J.Marenco/理论计算机科学电子笔记346（2019）557√ΣΣ一个这样的设置，起源于RPC的挑战性实例，是DNA阵列的合成[7]。作为该方法的一部分，光被选择性地允许通过掩模以暴露阵列中的细胞，从而激活该细胞中的核酸片段。用于DNA阵列的掩模由图案化设备构建，所述图案化设备通过一长串“散列”产生矩形区域由于掩模的成本与生成的矩形的数量成比例，所以期望具有最小数量的矩形这种技术类似于半导体工业中使用的基于半导体的集成电路掩模通常由正交多边形组成，每个边平行于其中一个轴，并且这些多边形必须被尽可能少的矩形覆盖[8]。RPC的另一个应用是处理访问控制列表（Access Control List，简称ACL）。在网络路由器中，路由器用于确定哪些到达的数据包应该转发到它们的目的地，哪些应该丢弃。ACL可以被视为（经过一些简化）一组元组（S，D，a），其中S和D是源地址和目的地址范围，并且a∈ {0， 1}是forward（1）或拒绝（0）操作。S和D由长度为w或更小的二进制字符串指定，其中w是IP地址的长度最小化的大小的路由器允许提高访问控制性能的当前国家的最先进的路由器。的一套规则ACL可以建模为2w× 2w矩阵，其中源IP地址和目的IP地址的每个组合都有一个条目（列和行的索引从0到2w− 1）。当且仅当以下情况下，ACL的操作可以视为在条目中设置1允许组合（即，转发），并且矩阵中具有值1的条目的最小矩形覆盖被称为ACL最小化问题[2]。最早提到RPC似乎是由于Masek[10]。在这项工作中，作者证明了RPC是NP难的; Berman和DasGupta后来证明了它是MaxSNP难的[4]。最好的多项式时间近似保证是O（ logk），其中k是输入矩阵[1]中具有值1的条目的数量。在[9]和[11]中，在多面体方法下也研究了该问题的稍微更一般的版本。在前者中，作者分析了新的下界的基础上的线性规划松弛的建议制定的分数解的最佳覆盖大小。后者讨论了凸多边形矩形覆盖的两个整数规划模型给定一个二元矩阵M∈ {0， 1}m×n，M中的一个矩形形式上定义为元素集{（k，l）：i1≤k≤i2andj1≤l≤j2}，其中1≤i1≤i2≤m，1≤j1≤j2≤n.我们定义R（M）为M中只包含M中值为1的元素的矩形的集合。对于每个r∈R（M），我们引入一个二元变量xr指定是否在封面中选择矩形R。 对于M ij = 1的每个条目（i，j），必须选择至少一个包含（i，j）的矩形，并且我们寻求最小化所选矩形的数量。minr∈R（M）xr（1）Mij≤r∈R（M）：（i，j）∈rx ri= 1，...，m，j = 1，...，n（2）I. Koch，J.Marenco/理论计算机科学电子笔记346（2019）557559Σi=i1≤xr∈ {0，1}r∈R（M）（3）R（M）中矩形的个数是多项式，即|R（M）|时间复杂度为O（n2m2）.然而，对于一个中型到大型的输入矩阵，这个公式很快导致不切实际的大量变量。在这种情况下，自然的解决方案是列生成方法，即，动态生成的矩形变量的线性松弛的制定时，强对偶性被违反。在这种情况下，列生成包括找到负减少成本的（加权）矩形。换句话说，我们在M内寻找一个最大权重的二维整数数组。这个问题的有效解决方案是必不可少的分支和价格计划，利用所描述的列生成。此外，上述公式的线性规划松弛被证明是非常紧的，如[9]中进行的实验所示。这使得分支和价格方法更有前途，因为它更有可能从搜索树中删除节点，从而加快搜索最优解的速度这两个参数激励我们的研究的最大2D子阵列多面体，这是这项工作的主要重点。2最大子阵问题给定一个d维实值数组A，d≥1，最大子数组问题在于找到A的一个连续且轴平行的部分，具有最大和。我们对d= 2的情况感兴趣，它对应于一个2维数组A∈ Rm×n，并要求行索引i1，i2∈ {1，.， m}，i1≤ i2，以及列索引j1，j2∈ {1，.，n}，j1≤j2，使得j2j=j1ij是最大值。我们假设m n。 Bentley描述的经典算法解决了这个问题时间复杂度为O（m2n）的问题[3]，随后的工作表明，这个问题可以在次立方时间内解决。实际上，[13]中提出的算法运行时间为O（m2n（log logm/ logm）12log（n/m）），并且在[12]中改进了这个界限，最坏情况为O（m2n（log logm/logm）12虽然是次立方的，但当m和n接近真实尺寸的图像时，这些算法可能没有实际用途。此外，在列生成环境中，我们不需要将列生成问题求解到最优，因为具有负降低成本的列可以继续该过程。因此，快速算法对于该问题可能是有用的，并且特别地，基于线性规划的算法（例如，四舍五入法）可能是感兴趣的。由于这些事实，我们有兴趣在整数规划为基础的方法为d= 2的最大子阵列问题在这项工作中，我们开始这样一个问题，通过探索与自然整数规划制定这个问题的多面体。这样一项工作的最终目标是确定有效不等式的强族，这些不等式在最大子阵列问题的切割平面过程中可能是有用的对于d= 2。通过在舍入阶段之前加强线性松弛，这种有效不等式族在基于线性规划的舍入启发式中也可以是有用的560I. Koch，J.Marenco/理论计算机科学电子笔记346（2019）557联系我们m，nΣm，nm，nIJIjΣ2相关联的多面体可以被认为是全区间向量多面体的二维版本，即，{0， 1}n中向量的凸包具有连续的1。文[6]中研究了相应的多面体，其结果启发了当前工作中的一些结果3二维子阵多面体我们考虑具有m行和n列的实值矩阵A表示为R={1，.，m}行索引的集合，并且通过C ={1，.，n}列索引的集合。我们还定义P=R×C为A的元素集合（在本文中也称为像素）。对于（i，j）∈P，当且仅当像素（i，j）属于所表示的矩形时，二进制变量xij取值1由Q（S）表示的像素集合S P的矩形外壳是包括S中的所有像素的最小矩形，即，Q（S）={（k，l）：min （i，j）∈Si≤k≤max（i，j）∈Si且min （i，j）∈Sj lmax（i，j）∈Sj.如果S=p，pJ当p=（i，j）且PJ=（iJ，jJ）时，则我们也用Q（p，PJ）和Q（i，j，iJ，jJ）表示Q（S 对于（i，j），（IJ，JJ）∈P，我们定义□（i，j，IJ，JJ）为可行解x∈ {0，1}mn，x kl= 1当且仅当（k，l）∈Q（i，j，IJ，jj）.定义3.1对于m∈ Z+和n∈ Z+， 我们定义PQ{□（i，j，i，j）：1≤i≤i≤n}。≤m且1≤j≤j= conv. {0}次J J Jm，nJ我们现在给出了一个公式的二维最大子阵列问题作为一个操作-PQ上的最小化问题 对于（i，j）∈P，Aij是与拾取像素（i，j）。在此设置中，2D最大子阵列问题可以是公式如下。Max（i，j）∈PAijxijxij+xi（j−2）≤xi（j−1）+1（i，j）∈P，j>2（4）xij+x（i−2）j≤x（i−1）j+1（i，j）∈P，i>2（5）X+x′ ′≤xij′+xi′j+1（i，j），（IJJJ）∈P，IIJ，JJJ（6）0个<0m，n>0个Σ<0m，n−110Qxijxij'xij'xij西杰xi'j'xi'j'西杰(a) （b）当j′> 3.使用与定理4.3相同的证明技巧，我们可以证明以下推广。定理4.8设π ∈ {-1，0，1}mn，|I π|为|I π|+1。 假设（a）每个像素π π1 −1可以从I 1中的某个像素到达。 如果存在列表L ={R1，R2，.， R k}的子矩形，使得（b）Iπ中的每个像素都包含在Ri中，对于某些i∈π π−1π{1，.，k}，（c）|R iI1|为|R iI−1| + 1，其中i = 1，.，k和（d）|I−1（R i\i−1Rj）|i=1， . ，k，nπx≤1对PQ是面诱导的.R1R2R3R4见图6。一个有效的不等式πx证明了定理4.8的假设。中的灰色矩形子图表示假设的列表L的矩形Ri。注意定理4.3的假设（b）不成立。有趣的是，定理4.8的假设（b）-（d）似乎是必要的，不等式πx≤ 1，其中π∈ {− 1，0，1}mn有|I π|为|I π|+11 −1并满足假设（a）。 我们进行了详尽的计算验证-借助于P-Q，P-Q和P-Q的所有分面诱导不等式，三，五四，四三、六PORTA[5]软件包。在所有情况下（约。7700分面诱导不平等PQ的9900个面诱导不等式，P Q的47500个面诱导不等式，三，五，四，四的关系）的列表L满足的假设确实被发现。由于不切实际的566I. Koch，J.Marenco/理论计算机科学电子笔记346（2019）5571m，n≤1−3m，n≤运行时，无法检查较大的实例。(b)系数在{-2，0， 1}和{-3，0， 1}现在我们来探讨至少有一个系数绝对值大于1的有效不等式。定理4.9设π∈ {−2，0，1}mn. 如果Iπ={（i1，j1），（i2，j2），（i3，j3）}，其中i1

下载后可阅读完整内容，剩余1页未读，立即下载