Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming
Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming
复制标题
整数规划的最优树深矩阵和行不变参数化算法
DOI：
10.4230/lipics.icalp.2020.26
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Kristýna Pekárková
中科院分区：
文献类型：
--
作者：
Timothy F. N. Chan;Jacob W. Cooper;Martin Koutecký;Daniel Král;Kristýna Pekárková
关于整数规划的固定参数易处理性的一系列研究最终表明，具有n个变量和树深度为d和最大条目Δ的约束矩阵的整数规划对于某个函数g在时间g（d，Δ）poly（n）中是可解的，即，当用树深度d和Δ参数化时，固定参数易于处理。然而，约束矩阵的树深度取决于其非零项的位置，因此不能反映其几何结构。特别地，约束矩阵的树深度不被行操作保留，即，给定的整数规划可以等效于具有较小的对偶树深度的另一个整数规划。
我们证明了由约束矩阵的列定义的拟阵的分支深度等于行等价矩阵的最小树深度。我们还设计了一个固定参数的算法参数化的整数d和输入矩阵的条目复杂度，要么输出一个矩阵的最小的对偶树深度是行等价的输入矩阵或输出，没有矩阵的对偶树深度最多d是行等价的输入矩阵。最后，我们利用这些结果得到一个固定参数算法的整数规划参数的分支深度的输入约束矩阵和条目的复杂性。分支深度的参数化不能被更宽松的分支宽度概念所取代。
A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with tree-depth d and largest entry Δ are solvable in time g(d,Δ) poly(n) for some function g, i.e., fixed parameter tractable when parameterized by tree-depth d and Δ. However, the tree-depth of a constraint matrix depends on the positions of its non-zero entries and thus does not reflect its geometric structure. In particular, tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth.
We prove that the branch-depth of the matroid defined by the columns of the constraint matrix is equal to the minimum tree-depth of a row-equivalent matrix. We also design a fixed parameter algorithm parameterized by an integer d and the entry complexity of an input matrix that either outputs a matrix with the smallest dual tree-depth that is row-equivalent to the input matrix or outputs that there is no matrix with dual tree-depth at most d that is row-equivalent to the input matrix. Finally, we use these results to obtain a fixed parameter algorithm for integer programming parameterized by the branch-depth of the input constraint matrix and the entry complexity. The parameterization by branch-depth cannot be replaced by the more permissive notion of branch-width.