首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

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

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

02
领券