.png){kind=icon}
.png){kind=icon}
Return
0/1 Knapsack problem on hyper hexa-cell interconnection network
.png){kind=icon}
PRE
AI
DOI：10.1007/s10586-025-05801-3.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The knapsack problem is a well-known problem, and it has various types, such as 0/1 knapsack, fractional knapsack, bounded knapsack, and unbounded knapsack, and many applications, such as resource allocation, investment decisions, scheduling and planning, and architectures for localization. The knapsack problem is a combinatorial optimization problem where one must maximize the profit of objects in a knapsack without exceeding its capacity. In this paper, we design and implement a parallel dynamic programming algorithm to solve the 0/1 knapsack problem on a hyper hexa-cell interconnection network. This algorithm is referred to as the PDPK-HHC. The proposed algorithm is assessed analytically and through simulations based on multiple performance indicators such as communication time, computation time, overall execution time, speedup, efficiency, and solution quality across different dataset sizes and types. The best simulation results show that under the largest simulated configuration, the PDPK-HHC algorithm reached solutions matching the expected dynamic-programming optimum and achieved up to 505× speedup at 768 processors on a 512 MB dataset; at 12 processors, efficiency reached up to 95% under the tested conditions, demonstrating better performance than its sequential counterpart under the tested conditions.
Keywords:
Knapsack problem
Dynamic programming
Hexa-cell network
Chained-cubic tree network
Mesh network
Interconnection network
Journal
C
IF:
0
Papers:
691
Citations:
1