A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles

DOI10.1016/j.amc.2007.10.045zbMath1147.65045OpenAlexW1968802784MaRDI QIDQ941476

S. Raja Balachandar, K. Kannan

Publication date: 1 September 2008

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2007.10.045

zbMATH Keywords

computational complexitynumerical examplesheuristicNP-hard problems0-1 multi-constrained knapsack problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Complexity and performance of numerical algorithms (65Y20)

Related Items (1)

A heuristic algorithm for resource allocation/reallocation problem

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A heuristic algorithm for the multidimensional zero-one knapsack problem
• A simulated annealing approach to the multiconstraint zero-one knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• An efficient tabu search approach for the 0-1 multidimensional knapsack problem
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• A heuristic solution procedure for the multiconstraint zero-one knapsack problem
• Pivot and Complement–A Heuristic for 0-1 Programming
• Approximate Algorithms for the 0/1 Knapsack Problem
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
• An Improved Heuristic for Multidimensional 0-1 Knapsack Problems
• The Theory and Computation of Knapsack Functions
• An Additive Algorithm for Solving Linear Programs with Zero-One Variables
• An Enumeration Algorithm for Knapsack Problems

This page was built for publication: A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles