Approximability of the two-stage stochastic knapsack problem with discretely distributed weights

DOI10.1016/j.dam.2013.02.015zbMath1295.90062MaRDI QIDQ2448903

Stefanie Kosuch

Publication date: 5 May 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.02.015

zbMATH Keywords

approximation algorithms; two-stage stochastic programming; stochastic knapsack problem; non-approximation

Mathematics Subject Classification ID

90C15: Stochastic programming

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem, The submodularity of two-stage stochastic maximum-weight independent set problems, Two-stage stochastic max-weight independent set problems, On the approximability of the two-phase knapsack problem, Robust recoverable and two-stage selection problems, Using 3D-printing in disaster response: the two-stage stochastic 3D-printing knapsack problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Knapsack problem with probability constraints
• The static stochastic knapsack problem with normally distributed item sizes
• A PTAS for the chance-constrained knapsack problem with random item sizes
• Approximation algorithms for knapsack problems with cardinality constraints
• Approximation for knapsack problems with multiple constraints
• Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation
• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• Computational complexity of stochastic programming problems
• Linear Programming under Uncertainty
• The Sample Average Approximation Method for Stochastic Discrete Optimization
• Linear degree extractors and the inapproximability of max clique and chromatic number
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• The stochastic single resource service-provision problem
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
• Approximation Algorithms for 2-Stage Stochastic Scheduling Problems
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits