The double exponential runtime is tight for 2-stage stochastic ILPs

DOI10.1007/s10107-022-01837-0OpenAlexW3082581272WikidataQ115606178 ScholiaQ115606178MaRDI QIDQ5925653

Alexandra Lassota, Klaus Jansen, Kim-Manuel Klein

Publication date: 14 March 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-022-01837-0

zbMATH Keywords

lower boundquadratic congruencesexponential time hypothesis2-stage stochastic ILPs

Mathematics Subject Classification ID

Integer programming (90C10)

Uses Software

• Mathematica

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(N\)-fold integer programming
• NP-complete decision problems for binary quadratics
• Decomposition of test sets in stochastic integer programming
• Which problems have strongly exponential complexity?
• Exact solutions to a class of stochastic generalized assignment problems
• Approximate formulas for some functions of prime numbers
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• A Polynomial-Time Algorithm for Optimizing over N-Fold 4-Block Decomposable Integer Programs
• A Priori Optimization of the Probabilistic Traveling Salesman Problem
• Two‐stage stochastic integer programming: a survey
• About the Complexity of Two-Stage Stochastic IPs
• Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding
• Parameterized Algorithms
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• On the complexity of \(k\)-SAT

This page was built for publication: The double exponential runtime is tight for 2-stage stochastic ILPs