About the complexity of two-stage stochastic IPs

DOI10.1007/S10107-021-01698-ZzbMATH Open1489.90064OpenAlexW3196963773MaRDI QIDQ2118129FDOQ2118129

Authors: Kim-Manuel Klein 

Publication date: 22 March 2022

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

Full work available at URL: https://doi.org/10.1007/s10107-021-01698-z

Recommendations

• About the Complexity of Two-Stage Stochastic IPs
• The double exponential runtime is tight for 2-stage stochastic ILPs
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Two-stage quadratic integer programs with stochastic right-hand sides
• scientific article; zbMATH DE number 1688600

zbMATH Keywords

integer programmingstochastic programmingtwo-stage stochasticparameterized compexity

Mathematics Subject Classification ID

Stochastic programming (90C15) Integer programming (90C10)

Cites Work

• Introduction to stochastic programming.
• Minkowski's Convex Body Theorem and Integer Programming
• On the foundations of linear and integer linear programming I
• Title not available (Why is that?)
• Value of the Steinitz constant
• Title not available (Why is that?)
• L-shaped decomposition of two-stage stochastic programs with integer recourse
• A finite branch-and-bound algorithm for two-stage stochastic integer programs
• Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs
• Two‐stage stochastic integer programming: a survey
• Scheduling meets \(n\)-fold integer programming
• Finiteness theorems in stochastic integer programming
• Title not available (Why is that?)
• Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs
• Analytical Evaluation of Hierarchical Planning Systems
• Decomposition of test sets in stochastic integer programming
• Combinatorial \(n\)-fold integer programming and applications
• Optimizing electricity distribution using two-stage integer recourse models
• Near-linear time algorithm for \(n\)-fold ILPs via color coding
• Faster Algorithms for Integer Programs with Block Structure
• Title not available (Why is that?)
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• Voting and bribing in single-exponential time
• Title not available (Why is that?)

Cited In (6)

• The double exponential runtime is tight for 2-stage stochastic ILPs
• Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
• FPT algorithms for a special block-structured integer program with applications in scheduling
• About the Complexity of Two-Stage Stochastic IPs
• An approximated dynamic programming model for the supply vessel fleet sizing problem
• Optimizing low dimensional functions over the integers

This page was built for publication: About the complexity of two-stage stochastic IPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118129)