A Parameterized Algorithm for 2-Stage Stochastic IPs with one row

We consider 2-stage stochastic integer linear problems (ILPs) with one row and identical first stage. For this case, we present separate algorithms for deciding the feasibility problem and for solving the optimization problem. For the feasibility problem, our algorithm achieves a running time which significantly improves upon state-of-the-art algorithms for general 2-stage stochastic ILPs such as Cslovjecsek et al. (SODA '24) when applied to our context. For the optimality problem, our algorithm yields a running time linear in the number of constraints and exponential in the largest entry of the constraint matrix. We achieve our results by novel use of structural properties to the ILPs we consider. Additionally, we provide an upper bound on the right hand side. We further complement our positive results by showing a lower bound on the running times of 2-stage stochastic ILPs with one row which follows via a bound derived from ETH.

 

Logo BII

Rights

Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.

Cite

Citation style:
Could not load citation form.