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

DOI10.1016/J.DAM.2013.02.015MaRDI QIDQ2448903zbMATH OpenOpenAlexFDO

Authors 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 algorithmsnon-approximationstochastic knapsack problemtwo-stage stochastic programming

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On two-stage stochastic knapsack problems
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• scientific article; zbMATH DE number 1114460
• Improved approximation results for stochastic knapsack problems
• Knapsack problem with probability constraints

Cites work

• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• A PTAS for the chance-constrained knapsack problem with random item sizes
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• Approximation Algorithms for 2-Stage Stochastic Scheduling Problems
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Approximation algorithms for knapsack problems with cardinality constraints
• Approximation for knapsack problems with multiple constraints
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
• Computational complexity of stochastic programming problems
• scientific article; zbMATH DE number 1114460 (Why is no real title available?)
• scientific article; zbMATH DE number 1175949 (Why is no real title available?)
• scientific article; zbMATH DE number 2084697 (Why is no real title available?)
• scientific article; zbMATH DE number 1559582 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 6469210 (Why is no real title available?)
• Improved approximation results for stochastic knapsack problems
• Knapsack problem with probability constraints
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear programming under uncertainty
• On the random 2-stage minimum spanning tree
• The sample average approximation method for stochastic discrete optimization
• The static stochastic knapsack problem with normally distributed item sizes
• The stochastic single resource service-provision problem
• Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation

Cited in

(7)

• 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
• On two-stage stochastic knapsack problems

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Approximability of the two-stage stochastic knapsack problem with discretely distributed weights

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