论文标题
对于2阶段随机ILP的双指数运行时间很紧
The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs
论文作者
论文摘要
我们考虑基本算法数字理论问题及其与一类结构化整数线性程序（ILP）的关系，称为$ 2 $ stage Attochantic。 $ 2 $ stage随机ILP是一个整数程序，其形式为$ \ min \ {c^t x x \ mid \ mathcal {a} x = b，\ ell \ ell \ ell \ leq x \ leq x \ leq leq u，x \ in \ mathbb {z} \ Mathbb {z}^{nt \ times r +ns} $由$ n $矩阵$ a_i \ in \ mathbb {z}^{z}^{t \ times r} $在垂直线上，$ n $ n $ n $矩阵$ b_i \ in \ in \ in \ in \ in \ mathbb {z} $ nix^$ nia^$ nia^$ nia plane pere tiame s} 首先，对于一个称为二次一致性的数字理论问题，我们显示出更强的硬度结果，其中目标是计算一个满足$ z^2 \equivα\equivα\ bmodβ$的数字$ z \ leqγ$，用于给定的$α，β，γ，γ\ in \ mathbb {z} $。这个问题被曼德斯和阿德曼在1978年已经证明是NP-HARD。但是，这种硬度仅适用于$β$的质量分解的实例。我们避免了这种必要性证明问题仍然是NP-HARD，即使每个质数仅经常发生。 Then, using this new hardness result for the Quadratic Congruences problem, we prove a lower bound of $2^{2^{δ(s+t)}} |I|^{O(1)}$ for some $δ> 0$ for the running time of any algorithm solving $2$-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH).在这里，$ | i | $是实例的编码长度。如果$ r $，$ || b || _ {\ infty} $，$ || c || _ {\ infty}，|| \ ell || _ {\ infty} $和最大的绝对值$δ$在约束矩阵$ \ m nathcal {a a}中是常数。这表明最新的算法几乎很紧。此外，这证明了这些ILP的确比密切相关的$ n $ fold Ilps更难解决的怀疑，而相关矩阵是$ \ mathcal a $ a $的转换。
We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called $2$-stage stochastic. A $2$-stage stochastic ILP is an integer program of the form $\min \{c^T x \mid \mathcal{A} x = b, \ell \leq x \leq u, x \in \mathbb{Z}^{r + ns} \}$ where the constraint matrix $\mathcal{A} \in \mathbb{Z}^{nt \times r +ns}$ consists of $n$ matrices $A_i \in \mathbb{Z}^{t \times r}$ on the vertical line and $n$ matrices $B_i \in \mathbb{Z}^{t \times s}$ on the diagonal line aside. First, we show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number $z \leq γ$ satisfying $z^2 \equiv α\bmod β$ for given $α, β, γ\in \mathbb{Z}$. This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of $β$ admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Then, using this new hardness result for the Quadratic Congruences problem, we prove a lower bound of $2^{2^{δ(s+t)}} |I|^{O(1)}$ for some $δ> 0$ for the running time of any algorithm solving $2$-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH). Here, $|I|$ is the encoding length of the instance. This result even holds if $r$, $||b||_{\infty}$, $||c||_{\infty}, ||\ell||_{\infty}$ and the largest absolute value $Δ$ in the constraint matrix $\mathcal{A}$ are constant. This shows that the state-of-the-art algorithms are nearly tight. Further, it proves the suspicion that these ILPs are indeed harder to solve than the closely related $n$-fold ILPs where the contraint matrix is the transpose of $\mathcal A$.
