LP Rounding Approximation Algorithms for Stochastic Network Design

DOI10.1287/MOOR.1060.0237MaRDI QIDQ5388034zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, R. Ravi, Amitabh Sinha

Publication date 27 May 2008

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.1060.0237

zbMATH Keywords

stochastic optimizationapproximation algorithmnetwork designSteiner treeprimal-dual methodLP rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic network models in operations research (90B15)

Recommendations

• Automata, Languages and Programming
• Two-stage robust network design with exponential scenarios
• Two-Stage Robust Network Design with Exponential Scenarios
• Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut
• Probabilistic models for the Steiner tree problem

Cited in

(15)

• Sampling-based approximation schemes for capacitated stochastic inventory control models
• On greedy approximation algorithms for a class of two-stage stochastic assignment problems
• Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut
• Sell or hold: A simple two-stage stochastic combinatorial optimization problem
• Improved bounds in stochastic matching and optimization
• Decomposition methods for the two-stage stochastic Steiner tree problem
• The discrete sell or hold problem with constraints on asset values
• Probabilistic analysis of an lp relaxation bound for the steiner problem in networks
• A unified framework for multistage mixed integer linear optimization
• Lagrange dual bound computation for stochastic service network design
• Network design for information networks
• Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms
• Approximation algorithms for stochastic and risk-averse optimization
• LP extreme points and cuts for the fixed-charge network design problem
• Stochastic survivable network design problems: theory and practice

This page was built for publication: LP Rounding Approximation Algorithms for Stochastic Network Design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5388034)