NDLI: Improved approximations for two-stage min-cut and shortest path problems under uncertainty

Content Provider	Springer Nature Link
Author	Golovin, Daniel Goyal, Vineet Ravi, R. Sysikaski, Mikko Polishchuk, Valentin
Copyright Year	2014
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. (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$$ -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 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.
Ending Page	194
Page Count	28
Starting Page	167
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1-2
Volume Number	149
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2014-01-12
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mathematical Methods in Physics Robust optimization Calculus of Variations and Optimal Control; Optimization Mathematics of Computing Approximation methods and heuristics Numerical Analysis Theoretical, Mathematical and Computational Physics Approximation algorithms Combinatorial optimization Combinatorics Stochastic programming
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bulk-Robust combinatorial optimization

Quadratic programming and combinatorial minimum weight product problems

Improved Approximations for Two-stage Min-Cut and Shortest Path Problems under Uncertainty (2014)

Robust optimization approach for a chance-constrained binary knapsack problem

Min–max–min robust combinatorial optimization

Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems (2006)

Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems (2006)

Tractable Approximations to Robust Conic Optimization Problems

Pay today for a rainy day: improved approximation algorithms for demand-robust min-cut and shortest path problems

Improved approximations for two-stage min-cut and shortest path problems under uncertainty

Similar Documents

Bulk-Robust combinatorial optimization

Quadratic programming and combinatorial minimum weight product problems

Improved Approximations for Two-stage Min-Cut and Shortest Path Problems under Uncertainty (2014)

Robust optimization approach for a chance-constrained binary knapsack problem

Min–max–min robust combinatorial optimization

Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems (2006)

Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems (2006)

Tractable Approximations to Robust Conic Optimization Problems

Pay today for a rainy day: improved approximation algorithms for demand-robust min-cut and shortest path problems

Improved approximations for two-stage min-cut and shortest path problems under uncertainty