An extension of Dembo–Hammer’s reduction algorithm for the 0-1 knapsack problem

Dembo–Hammer’s Reduction (DHR) algorithm is one of the classical algorithms for the 0-1 Knapsack Problem (0-1 KP) and its variants, which reduces an instance of the 0-1 KP to a sub-instance of smaller size with reduction time complexity [Formula: see text]. We present an extension of DHR (abbreviated as EDHR), which reduces an instance of 0-1[Formula: see text]KP to at most [Formula: see text] sub-instances for any positive integer [Formula: see text]. In practice, parameter [Formula: see text] can be set as needed. In particular, if we choose [Formula: see text] then EDHR is exactly DHR. Finally, computational experiments on randomly generated data instances demonstrate that EDHR substantially reduces the search tree size compared to CPLEX.