Average-case performance of rollout algorithms for knapsack problems

DOI10.1007/s10957-014-0603-xzbMath1330.90063arXiv1301.4529OpenAlexW2158588309MaRDI QIDQ2349849

Andrew Mastin, Patrick Jaillet

Publication date: 18 June 2015

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.4529

zbMATH Keywords

knapsack problemapproximate dynamic programmingrollout algorithmssubset sum problem

Mathematics Subject Classification ID

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

Related Items

A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs ⋮ Optimal setup of a multihead weighing machine

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum and worst-case performance ratios of rollout algorithms
• Probabilistic analysis of the subset-sum problem
• The average behaviour of greedy algorithms for the knapsack problem: general distributions
• Rollout algorithms for stochastic scheduling problems
• Stochastic analysis of greedy algorithms for the subset sum problem
• Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
• Rollout algorithms for combinatorial optimization
• Worst-case analysis of greedy algorithms for the subset-sum problem
• The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem
• A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands
• Neuro-Dynamic Programming: An Overview and Recent Results
• Random knapsack in expected polynomial time

This page was built for publication: Average-case performance of rollout algorithms for knapsack problems