Minimum and worst-case performance ratios of rollout algorithms

DOI10.1007/S10957-011-9902-7MaRDI QIDQ415370zbMATH OpenOpenAlexFDO

Authors Luca Bertazzi

Publication date 8 May 2012

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

Full work available at URL https://doi.org/10.1007/s10957-011-9902-7

zbMATH Keywords

minimum performance ratiorollout algorithmsworst-case performance ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Average-case performance of rollout algorithms for knapsack problems
• AN APPROACH FOR WORST CASE ANALYSIS OF HEURISTICS : ANALYSIS OF A FLEXIBLE 0-1 KNAPSACK PROBLEM
• A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs
• Rollout algorithms for combinatorial optimization
• New Rollout Algorithms for Combinatorial Optimization Problems

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 1321699 (Why is no real title available?)
• A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands
• A new fully polynomial time approximation scheme for the Knapsack problem
• An approximate dynamic programming approach for the vehicle routing problem with stochastic demands
• An approximate dynamic programming approach to multidimensional knapsack problems
• Analysis of a rollout approach to sequencing problems with stochastic routing applications
• Approximate Algorithms for the 0/1 Knapsack Problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Hybrid rollout approaches for the job shop scheduling problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Parallelization strategies for rollout algorithms
• Rollout algorithms for combinatorial optimization
• Rollout algorithms for stochastic scheduling problems

Cited in

(7)

• Rollout algorithms for combinatorial optimization
• Faster rollout search for the vehicle routing problem with stochastic demands and restocking
• New Rollout Algorithms for Combinatorial Optimization Problems
• Average-case performance of rollout algorithms for knapsack problems
• Expectation analysis for bounding solutions of the 0-1 knapsack problem
• A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs
• Patient scheduling in hemodialysis service

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Minimum and worst-case performance ratios of rollout algorithms

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