Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem

DOI10.1016/j.ins.2016.07.037zbMath1428.90144OpenAlexW2480227031MaRDI QIDQ2282074

Wenbin Li, Yu-Lin He, Shu-Liang Zhao, Yi-Chao He, Xi-Zhao Wang

Publication date: 6 January 2020

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2016.07.037

zbMATH Keywords

dynamic programmingexact algorithmparticle swarm optimizationapproximate algorithmdiscounted \(\{0\text{-}1\}\) knapsack problem

Mathematics Subject Classification ID

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

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Balancing the profit and capacity under uncertainties: a target‐based distributionally robust knapsack problem ⋮ On approximating the incremental knapsack problem ⋮ Approximating the 3-period incremental knapsack problem ⋮ Heuristic and exact reduction procedures to solve the discounted 0-1 knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A novel hybrid multi-objective immune algorithm with adaptive differential evolution
• Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem
• Design and analysis of approximation algorithms
• The quadratic knapsack problem -- a survey
• A hybrid algorithm for the unbounded knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
• The Design of Approximation Algorithms
• Convergent Analysis and Algorithmic Improvement of Differential Evolution
• Algorithms
• Algorithms for randomized time-varying knapsack problems