Submitted to Math Programming, manuscript No. Improved Approximations for Two-stage Min-Cut and Shortest Path Problems under Uncertainty

Abstract In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. [6], and give approximation algorithms with improved approximation factors. Specifically, we give a 2-approximation for the robust min-cut problem and a 4-approximation for the stochastic version. For the two-stage shortest path problem, we give a 3.39-approximation for the robust version and 6.78-approximation for the stochastic version. Our results significantly improve the previous best approximation factors for the problems. In particular, we provide the first constant-factor approximation for the stochastic min-cut problem. Our algorithms are based on guess and prune strategy that crucially exploits the nature of the robust and stochastic objective. In particular, we guess the worst-case second stage cost and based on the guess, select a subset of costly scenarios for the first-stage solution to address. The second-stage solution for any scenario is simply the min-cut (or shortest Part of this work was done while D. Golovin was affiliated with Carnegie Mellon University and was sup