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

DOI10.1007/978-3-030-73879-2_21zbMath1482.90122arXiv2008.12928OpenAlexW3160977836MaRDI QIDQ5918430

Alexandra Lassota, Klaus Jansen, Kim-Manuel Klein

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.12928

zbMATH Keywords

lower boundquadratic congruencesexponential time hypothesis2-stage stochastic ILPs

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items (2)

Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs

Cites Work

• Unnamed Item
• 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
• 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
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding
• Parameterized Algorithms
• The double exponential runtime is tight for 2-stage stochastic ILPs
• On the complexity of \(k\)-SAT

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