Improved approximations for robust mincut and shortest path

Valentin Polishchuk, Mikko Sysikaski

In two-stage robust optimization the solution to a problem is built in two stages: In the first stage a partial, not necessarily feasible, solution is exhibited. Then the adversary…