A PTAS for the chance-constrained knapsack problem with random item sizes

DOI10.1016/j.orl.2010.01.003zbMath1187.90232OpenAlexW1976174751MaRDI QIDQ974983

Vineet Goyal, R. Ravi

Publication date: 8 June 2010

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2010.01.003

zbMATH Keywords

approximation schemesstochastic knapsackchance constraint

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

Related Items (24)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Robust optimization approach for a chance-constrained binary knapsack problem ⋮ Exact algorithms for the 0-1 time-bomb knapsack problem ⋮ Piecewise static policies for two-stage adjustable robust linear optimization ⋮ Relaxations and approximations of chance constraints under finite distributions ⋮ Gamma distribution approach in chance-constrained stochastic programming model ⋮ Adaptivity in the stochastic blackjack knapsack problem ⋮ Balancing the profit and capacity under uncertainties: a target‐based distributionally robust knapsack problem ⋮ Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness ⋮ A polynomial-time algorithm for a nonconvex chance-constrained program under the normal approximation ⋮ On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints ⋮ Bicriteria Approximation of Chance-Constrained Covering Problems ⋮ The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature ⋮ Approximability of the two-stage stochastic knapsack problem with discretely distributed weights ⋮ Lifting of probabilistic cover inequalities ⋮ Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem ⋮ Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes ⋮ Unnamed Item ⋮ A fully polynomial-time approximation scheme for approximating a sum of random variables ⋮ Convexity and Solutions of Stochastic Multidimensional 0-1 Knapsack Problems with Probabilistic Constraints ⋮ Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems ⋮ Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• The Dynamic and Stochastic Knapsack Problem with Deadlines

This page was built for publication: A PTAS for the chance-constrained knapsack problem with random item sizes