用于整数规划的行不变参数化算法

作者：Martin Koutecky,Daniel Kral

摘要：对整数规划的固定参数可处理性的长期研究最终表明，具有n个变量的整数程序和具有树深d和最大条目D的约束矩阵在时间g（d，D）poly（n）中是可解的。一些函数g，即，当由树深d和D参数化时，固定参数易处理。但是，约束矩阵的树深度取决于其非零项的位置，因此不反映其几何性质，特别是，在行操作下不是不变的。我们考虑通过名为branch-depth的matroid参数对约束矩阵进行参数化，该参数在行操作下是不变的。我们的主要结果断言，矩阵具有分支深度d和最大条目D的整数程序在时间f（d，D）poly（n）中是可解的。由于每个树深度较小的约束矩阵都具有较小的分支深度，因此我们的结果扩展了上述结果。分支深度的参数化不能被更宽松的分支宽度概念所取代。

原文标题：A row-invariant parameterized algorithm for integer programming

原文摘要：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 D are solvable in in time g(d,D)poly(n) for some function g, i.e., fixed parameter tractable when parameterized by tree-depth d and D. However, the tree-depth of a constraint matrix depends on the positions of its non-zero entries and thus does not reflect its geometric nature, in particular, is not invariant under row operations. We consider a parameterization of the constraint matrix by a matroid parameter called branch-depth, which is invariant under row operations. Our main result asserts that integer programs whose matrix has branch-depth d and largest entry D are solvable in time f(d,D)poly(n). Since every constraint matrix with small tree-depth has small branch-depth, our result extends the result above. The parameterization by branch-depth cannot be replaced by the more permissive notion of branch-width.

地址：https://arxiv.org/abs/1907.06688