An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910992244408320 |
|---|---|
| author | Yang, Yang |
| author_facet | Yang, Yang |
| contents | Dembo-Hammer's Reduction Algorithm (DHR) 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 $O(n)$. We present an extension of DHR (abbreviated as EDHR), which reduces an instance of 0-1 KP to at most $n^i$ sub-instances for any positive integer $i$. In practice, $i$ can be set as needed. In particular, if we choose $i=1$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06138 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem Yang, Yang Computational Complexity Data Structures and Algorithms Dembo-Hammer's Reduction Algorithm (DHR) 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 $O(n)$. We present an extension of DHR (abbreviated as EDHR), which reduces an instance of 0-1 KP to at most $n^i$ sub-instances for any positive integer $i$. In practice, $i$ can be set as needed. In particular, if we choose $i=1$ 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. |
| title | An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.06138 |