Relaxation analysis for the dynamic knapsack problem with stochastic item sizes

DOI10.1137/16M1101209MaRDI QIDQ4646440zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Blado, Alejandro Toriello

Publication date 14 January 2019

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/16m1101209

zbMATH Keywords

asymptotic analysisdynamic programsemi-infinite linear programstochastic knapsack

Mathematics Subject Classification ID

Semi-infinite programming (90C34) Markov and semi-Markov decision processes (90C40)

Recommendations

• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
• A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
• The static stochastic knapsack problem with normally distributed item sizes
• Improved approximation results for stochastic knapsack problems
• The Dynamic and Stochastic Knapsack Problem with Deadlines

Cites work

• A Preference Order Dynamic Program for a Knapsack Problem with Stochastic Rewards
• A PTAS for the chance-constrained knapsack problem with random item sizes
• A Renewal Decision Problem
• Adaptivity and approximation for stochastic packing problems
• Allocating Bandwidth for Bursty Connections
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Generalized polynomial approximations in Markovian decision processes
• Geometric algorithms and combinatorial optimization.
• scientific article; zbMATH DE number 44282 (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?)
• Improved approximation results for stochastic knapsack problems
• Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract
• Preference Order Stochastic Knapsack Problems: Methodological Issues
• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• Stochastic linear knapsack programming problem and its application to a portfolio selection problem
• The adaptive Knapsack problem with stochastic rewards
• The dynamic and stochastic knapsack problem
• The Dynamic and Stochastic Knapsack Problem with Deadlines
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• The Linear Programming Approach to Approximate Dynamic Programming
• The static stochastic knapsack problem with normally distributed item sizes

Cited in

(8)

• Dynamic node packing
• A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
• A logarithmic descent direction algorithm for the quadratic knapsack problem
• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• Adaptive Bin Packing with Overflow
• Expectation analysis for bounding solutions of the 0-1 knapsack problem
• Mixed-integer linear programming approximations for the stochastic knapsack

This page was built for publication: Relaxation analysis for the dynamic knapsack problem with stochastic item sizes

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