Hedging uncertainty: approximation algorithms for stochastic optimization problems

DOI10.1007/s10107-005-0673-5zbMath1098.90046OpenAlexW2112058494MaRDI QIDQ2494510

Amitabh Sinha, R. Ravi

Publication date: 28 June 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2027.42/45871

Mathematics Subject Classification ID

Continuous location (90B85) Stochastic programming (90C15) Combinatorial optimization (90C27)

Related Items

Approximation algorithms for stochastic combinatorial optimization problems ⋮ On stochastic \(k\)-facility location ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Approximation algorithms for \(k\)-level stochastic facility location problems ⋮ An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem ⋮ An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties ⋮ Approximation algorithm for the stochastic prize-collecting set multicover problem ⋮ An approximation algorithm for the \(k\)-level stochastic facility location problem ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ On the approximability of robust spanning tree problems ⋮ Approximation algorithms for the fault-tolerant facility location problem with penalties ⋮ The facility location problem with maximum distance constraint ⋮ Two-stage robust network design with exponential scenarios ⋮ Approximation algorithm for squared metric two-stage stochastic facility location problem ⋮ Stochastic uncapacitated hub location ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Sell or hold: A simple two-stage stochastic combinatorial optimization problem ⋮ A priori TSP in the Scenario Model ⋮ A primal-dual approximation algorithm for stochastic facility location problem with service installation costs ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ The discrete sell or hold problem with constraints on asset values ⋮ Stochastic survivable network design problems: theory and practice ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ Improved bounds in stochastic matching and optimization ⋮ A per-scenario bound for the two-stage stochastic facility location problem with linear penalty ⋮ Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation ⋮ An improved per-scenario bound for the two-stage stochastic facility location problem ⋮ Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty ⋮ Approximation algorithm for stochastic set cover problem ⋮ A priori TSP in the scenario model ⋮ LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem ⋮ An approximation algorithm for the stochastic fault-tolerant facility location problem ⋮ Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models ⋮ A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties ⋮ A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ Approximation algorithms for the stochastic priority facility location problem

Uses Software

• PICO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Bin packing can be solved within 1+epsilon in linear time
• Approximation algorithms for combinatorial problems
• Approximation algorithms and relaxations for a service provision problem on a telecommunication network
• Scenario reduction algorithms in stochastic programming
• Primal-dual algorithms for connected facility location problems
• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• Improved low-degree testing and its applications
• Approximation in stochastic scheduling
• Boosted sampling
• On Two-Stage Stochastic Minimum Spanning Trees
• A Dual-Based Procedure for Stochastic Facility Location
• Greedy Strikes Back: Improved Facility Location Algorithms
• Introduction to Stochastic Programming
• Two‐stage stochastic integer programming: a survey
• Allocating Bandwidth for Bursty Connections
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Provisioning a virtual private network
• Stochastic Machine Scheduling with Precedence Constraints
• Some optimal inapproximability results
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Integer Programming and Combinatorial Optimization
• Automata, Languages and Programming

This page was built for publication: Hedging uncertainty: approximation algorithms for stochastic optimization problems