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

DOI10.1007/11672142_16zbMath1136.68624OpenAlexW1579892319MaRDI QIDQ5449799

R. Ravi, Daniel Golovin, Vineet Goyal

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11672142_16

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (8)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ On the approximability of robust spanning tree problems ⋮ Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms ⋮ Two-stage robust network design with exponential scenarios ⋮ An \(s\)-\(t\) connection problem with adaptability ⋮ Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty ⋮ Bulk-robust combinatorial optimization

This page was built for publication: Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems