Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes

DOI10.1137/16M1101209zbMath1411.90340OpenAlexW2907351660WikidataQ128663039 ScholiaQ128663039MaRDI QIDQ4646440

Alejandro Toriello, Daniel Blado

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 analysisstochastic knapsackdynamic programsemi-infinite linear program

Mathematics Subject Classification ID

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

Related Items (5)

Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ 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 ⋮ Dynamic node packing ⋮ Adaptive Bin Packing with Overflow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The static stochastic knapsack problem with normally distributed item sizes
• A PTAS for the chance-constrained knapsack problem with random item sizes
• Generalized polynomial approximations in Markovian decision processes
• Stochastic linear knapsack programming problem and its application to a portfolio selection problem
• Geometric algorithms and combinatorial optimization.
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The Dynamic and Stochastic Knapsack Problem
• Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes
• TECHNICAL NOTE—The Adaptive Knapsack Problem with Stochastic Rewards
• A Preference Order Dynamic Program for a Knapsack Problem with Stochastic Rewards
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• The Linear Programming Approach to Approximate Dynamic Programming
• Preference Order Stochastic Knapsack Problems: Methodological Issues
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• A Renewal Decision Problem
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• The Dynamic and Stochastic Knapsack Problem with Deadlines
• Allocating Bandwidth for Bursty Connections
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

This page was built for publication: Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes