论文标题
背包交点层次结构适用于树木中的全有或无所不在
A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees
论文作者
论文摘要
我们介绍了一个自然的背包交叉层次结构，用于增强包装整数程序的线性编程放松，即，$ \ max \ {w^tx：x \ in p \ cap \ {0,1 \}^n \} $ $ a，b，w \ ge0 $。 $ t^{th} $级别$ p^{t} $对应于添加与任何$ t $ knapsack约束（约束矩阵的行）相交的整数相关的切割。该型号捕获了“ $ t $ - 行切割”的最大强度，这是求解器通常用于小$ t $的一种方法。如果$ a $是$ m \ times n $，则$ p^m $是$ p $的整数船体，$ p^1 $对应于为每个关联的单行背包问题添加削减。因此，即使超过$ p^1 $，也是np-hard。但是，对于固定的$ t $和任何$ε> 0 $，Pritchard的结果意味着$ p^{t} $的poly time $（1+ε）$ - 近似。然后，我们在树木中研究了全有或全无的流问题的背景下（也称为树上的流动），研究了层次结构的强度。对于此问题，我们表明$ p^t $的完整性差距为$ O（n/t）$，并给出示例，其中差距为$ω（n/t）$。然后，我们检查更强的公式$ p _ {\ text {rank}} $，其中添加了所有等级约束。对于$ p _ {\ text {rank}}^t $，我们的最佳下限下降到$ω（1/c）$ f level $ t = n^c $，对于任何$ c> 0 $。此外，由于Friggstad和Gao，在一类著名的“坏实例”中，我们表明我们可以实现这一差距。因此，以$ n^c $的级别获得了这些实例的恒定完整差距。
We introduce a natural knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs, i.e., $\max\{w^Tx:x\in P\cap\{0,1\}^n\}$ where $P=\{x\in[0,1]^n:Ax \leq b\}$ and $A,b,w\ge0$. The $t^{th}$ level $P^{t}$ corresponds to adding cuts associated with the integer hull of the intersection of any $t$ knapsack constraints (rows of the constraint matrix). This model captures the maximum possible strength of "$t$-row cuts", an approach often used by solvers for small $t$. If $A$ is $m \times n$, then $P^m$ is the integer hull of $P$ and $P^1$ corresponds to adding cuts for each associated single-row knapsack problem. Thus, even separating over $P^1$ is NP-hard. However, for fixed $t$ and any $ε>0$, results of Pritchard imply there is a polytime $(1+ε)$-approximation for $P^{t}$. We then investigate the hierarchy's strength in the context of the well-studied all-or-nothing flow problem in trees (also called unsplittable flow on trees). For this problem, we show that the integrality gap of $P^t$ is $O(n/t)$ and give examples where the gap is $Ω(n/t)$. We then examine the stronger formulation $P_{\text{rank}}$ where all rank constraints are added. For $P_{\text{rank}}^t$, our best lower bound drops to $Ω(1/c)$ at level $t=n^c$ for any $c>0$. Moreover, on a well-known class of "bad instances" due to Friggstad and Gao, we show that we can achieve this gap; hence a constant integrality gap for these instances is obtained at level $n^c$.
