Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items

DOI10.1016/J.COR.2023.106281MaRDI QIDQ6106591zbMATH OpenFDO

Authors M. Lalou, H. Kheddouci

Publication date 3 July 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COR.2023.106281

zbMATH Keywords

complexityconstrained knapsack problemdirected acyclic graphsdynamic programmingin-treesout-trees

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Recommendations

• scientific article; zbMATH DE number 4093181
• A pseudo-polynomial time algorithm for solving the knapsack problem in polynomial space
• scientific article; zbMATH DE number 710573
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• scientific article; zbMATH DE number 1418266
• Pseudopolynomial algorithms for the solution of backpack problems
• An exact algorithm for 0-1 polynomial Knapsack problems
• The fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem

Cites work

• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• A dynamic programming algorithm for the knapsack problem with setup
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• An exact approach for the 0-1 knapsack problem with setups
• Approximation of knapsack problems with conflict and forcing graphs
• Exact approaches for the knapsack problem with setups
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Hypergraph theory. An introduction
• Improved dynamic programming and approximation results for the knapsack problem with setups
• Introduction to algorithms
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Knapsack problems with dependencies through non-additive measures and Choquet integral
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Optimization algorithms for the disjunctively constrained knapsack problem
• Partially ordered knapsack and applications to scheduling
• Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem
• Reducibility among combinatorial problems
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• Subset sum problems with digraph constraints
• Subset sum problems with special digraph constraints
• The 1-Neighbour Knapsack Problem
• The critical node detection problem in networks: a survey
• The dynamic and stochastic knapsack problem
• The knapsack problem with neighbour constraints
• The knapsack problem with special neighbor constraints
• The multidimensional knapsack problem: structure and algorithms
• The Multiple-Choice Knapsack Problem
• The Transitive Reduction of a Directed Graph
• Where are the hard knapsack problems?

Cited in

(2)

• Pseudopolynomial algorithms for the solution of backpack problems
• Knapsack problems with position-dependent item weights or profits

This page was built for publication: Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items

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