Showing 2021Show all
2 papers · 1 filter
cs.DS2021
Collapsing the Tower -- On the Complexity of Multistage Stochastic IPs
Kim-Manuel Klein, Janina Reuter
In this paper we study the computational complexity of solving a class of block structured integer programs (IPs) - so called multistage stochastic IPs. A multistage stochastic IP…
cs.DS2021
On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem
Kim-Manuel Klein
Consider positive integral solutions to the equation . In the so called unbounded subset sum problem, the objective is to d…