liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Improved approximations for two-stage min-cut and shortest path problems under uncertainty
Google, Pittsburgh, PA, USA .
Department of Industrial Engineering and Operations Research, Columbia University, Upper Manhattan, NY, USA .
Department of Computer Science, Helsinki Institute for Information Technology, University of Helsinki, Helsinki, Finland .
Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, USA .
Show others and affiliations
2015 (English)In: Mathematical Programming, ISSN 0025-5610, Vol. 149, no 1, 167-194 p.Article in journal (Refereed) PublishedText
Abstract [en]

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. (in How to pay, come what may: approximation algorithms for demand-robust covering problems. In: FOCS, pp 367–378, 2005), 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'>3.39 3.39 -approximation for the robust version and 6.78'>6.78 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 a 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 path) problem in the residual graph. The key contribution is to show that there is a near-optimal first-stage solution that completely satisfies the subset of costly scenarios that are selected by our procedure. While the guess and prune strategy is not directly applicable for the stochastic versions, we show that using a novel LP formulation, we can adapt a guess and prune algorithm for the stochastic versions. Our algorithms based on the guess and prune strategy provide insights about the applicability of this approach for more general robust and stochastic versions of combinatorial problems.

Place, publisher, year, edition, pages
2015. Vol. 149, no 1, 167-194 p.
Keyword [en]
Robust optimization – Combinatorial optimization – Approximation algorithms
National Category
Computational Mathematics
URN: urn:nbn:se:liu:diva-128017DOI: 10.1007/s10107-013-0742-0OAI: diva2:928742
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-05-26

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Polishchuk, Valentin
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 68 hits
ReferencesLink to record
Permanent link

Direct link