Two-stage robust network design with exponential scenarios

DOI10.1007/s00453-011-9596-0zbMath1266.68031OpenAlexW2076901012MaRDI QIDQ1939662

Rohit Khandekar, Guy Kortsarz, Mohammad R. Salavatipour, Vahab S. Mirrokni

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9596-0

zbMATH Keywords

approximation algorithmshardness of approximationrobust network designrobust facility locationrobust Steiner forestrobust Steiner tree

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ K-Adaptability in Two-Stage Robust Binary Programming ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Universal Algorithms for Clustering Problems ⋮ Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms ⋮ Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty ⋮ On the power of static assignment policies for robust facility location problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Linear Programming under Uncertainty
• An improved LP-based approximation for steiner tree
• Boosted sampling
• Thresholded Covering Algorithms for Robust and Max-min Optimization
• The Complexity of Multiterminal Cuts
• Robust Combinatorial Optimization with Exponential Scenarios
• Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems

This page was built for publication: Two-stage robust network design with exponential scenarios