论文标题
块结构整数编程：我们可以在没有最大系数的情况下进行参数化吗？
Block-structured Integer Programming: Can we Parameterize without the Largest Coefficient?
论文作者
论文摘要
我们考虑4块$ n $ fold Integer编程，可以写为$ \ max \ {w \ cdot x：h x = b，l \ le x \ le x \ le u，in \ in \ mathbb {z}^{n} {n} {n} {n} \} $ constrinage matrix matrix $ h $在其中组成的小$ h $ ys $ bextrix $ copt $ bextrices $ y $ $（c，d，d，\ cdots，d）$，$ h $的第一列为$（c，b，b，\ cdots，b）$，$ h $的主要对角线为$（c，a，a，a，a，\ cdots，a）$，其他所有条目为$ 0 $。 $ b = c = 0 $的特殊情况称为$ n $ - 折叠整数编程。 4块$ n $ fold Integer编程及其特殊情况的先前算法结果通常为$δ$，这是$ H $中最大的绝对值作为参数的一部分。在本文中，我们探讨了从参数中摆脱$δ$的可能性，即，我们正在寻找以$ \logΔ$多价运行的算法。我们表明，假设$ \ text {p} \ neq \ text {np} $，即使$ a =（1,1，δ）$和$ b = c = 0 $，这也是不可能的。但是，如果$ a =（1,1，\ cdots，1）$或$ a \ in \ in \ mathbb {z}^{1 \ times 2} $，或者更一般的如果$ a \ in \ in \ mathbb {z}^{z}^{s_a \ times t_a} $ \ text {rank}（a）= s_a $。更确切地说 1。如果$ a =（1，\ ldots，1）\ in \ Mathbb {z}^{1 \ times t_a} $，则可以在$（t_a+t_a+t_a+t_a+t_a+t_b）} \ cdot py poly（n，\ log log log log log log log log log log log log log log dime $（t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+time）中解决4块$ n $ fold IP。 2。如果$ a \ in \ mathbb {z}^{s_a \ times t_a} $，$ t_a = s_a = s_a+1 $和$ \ text {rank}（a）= s_a $，然后可以在$（t_a+t_a+t_b）^cd_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_a+t_A n^{o（t_a）} \ cdot poly（\logδ）$ time;具体来说，如果我们还有$ b = c = 0 $（即$ n $ fold Integer编程），则可以在线性时间$ n \ cdot poly（t_a，\logδ）$中求解。
We consider 4-block $n$-fold integer programming, which can be written as $\max\{w\cdot x: H x=b, l\le x\le u, x\in \mathbb{Z}^{N} \}$ where the constraint matrix $H$ is composed of small submatrices $A,B,C,D$ such that the first row of $H$ is $(C,D,D,\cdots,D)$, the first column of $H$ is $(C,B,B,\cdots,B)$, the main diagonal of $H$ is $(C,A,A,\cdots,A)$, and all the other entries are $0$. The special case where $B=C=0$ is known as $n$-fold integer programming. Prior algorithmic results for 4-block $n$-fold integer programming and its special cases usually take $Δ$, the largest absolute value among entries of $H$ as part of the parameters. In this paper, we explore the possibility of getting rid of $Δ$ from parameters, i.e., we are looking for algorithms that runs polynomially in $\logΔ$. We show that, assuming $\text{P}\neq \text{NP}$, this is not possible even if $A=(1,1,Δ)$ and $B=C=0$. However, this becomes possible if $A=(1,1,\cdots,1)$ or $A\in \mathbb{Z}^{1\times 2}$, or more generally if $A\in\mathbb{Z}^{s_A\times t_A} $ where $t_A=s_A+1$ and the rank of matrix $A$ satisfies that $\text{rank}(A)=s_A$. More precisely, 1. If $A=(1,\ldots,1)\in \mathbb{Z}^{1\times t_A} $, then 4-block $n$-fold IP can be solved in $(t_A+t_B)^{O(t_A+t_B)}\cdot poly(n,\logΔ)$ time. 2. If $A\in\mathbb{Z}^{s_A\times t_A} $, $t_A=s_A+1$ and $\text{rank}(A)=s_A$, then 4-block $n$-fold IP can be solved in $(t_A+t_B)^{O(t_A+t_B)}\cdot n^{O(t_A)}\cdot poly(\logΔ)$ time; Specifically, if in addition we have $B=C=0$ (i.e., $n$-fold integer programming), then it can be solved in linear time $n\cdot poly(t_A,\log Δ)$.
