Back to Search
Start Over
The double exponential runtime is tight for 2-stage stochastic ILPs.
The double exponential runtime is tight for 2-stage stochastic ILPs.
- Source :
-
Mathematical Programming . Feb2023, Vol. 197 Issue 2, p1145-1172. 28p. - Publication Year :
- 2023
-
Abstract
- 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 ∣ A x = b , ℓ ≤ x ≤ u , x ∈ Z r + n s } where the constraint matrix A ∈ Z n t × r + n s consists of n matrices A i ∈ Z t × r on the vertical line and n matrices B i ∈ Z t × s on the diagonal line aside. We show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number z ≤ γ satisfying z 2 ≡ α mod β for given α , β , γ ∈ 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. Using this new hardness result for the Q U A D R A T I C C O N G R U E N C E S 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 | | ∞ , | | c | | ∞ , | | ℓ | | ∞ and the largest absolute value Δ in the constraint matrix 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 constraint matrix is the transpose of A . [ABSTRACT FROM AUTHOR]
- Subjects :
- *PRIME numbers
*ABSOLUTE value
*NP-hard problems
*STOCHASTIC matrices
*INTEGERS
Subjects
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 197
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 161716900
- Full Text :
- https://doi.org/10.1007/s10107-022-01837-0