Computing block-angular Karmarkar projections with applications to stochastic programming

The authors present a variant of Karmarkar’s algorithm for block-angular structured linear programs, such as stochastic linear programs. By computing the projection efficiently, they give a worst-case bound on the order of the running time that can be an order of magnitude better than that of Karmarkar’s standard algorithm. Further implications for approximations and very large-scale problems are given.