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.

Authors :
Jansen, Klaus
Klein, Kim-Manuel
Lassota, Alexandra
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]

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