A Scalable GPU-based Approach to Accelerate the Multiple-Choice Knapsack Problem

Bharath Suri, Unmesh D. Bordoloi, Petru Eles
Delopt, India
Design Automation and Test in Europe (DATE12), 2012


   title={A Scalable GPU-based Approach to Accelerate the Multiple-Choice Knapsack Problem},

   author={Suri, B. and Bordoloi, U.D. and Eles, P.},



Download Download (PDF)   View View   Source Source   



Variants of the 0-1 knapsack problem manifest themselves at the core of several system-level optimization problems. The running times of such system-level optimization techniques are adversely affected because the knapsack problem is NP-hard. In this paper, we propose a new GPU-based approach to accelerate the multiple-choice knapsack problem, which is a general version of the 0-1 knapsack problem. Apart from exploiting the parallelism offered by the GPUs, we also employ a variety of GPU-specific optimizations to further accelerate the running times of the knapsack problem. Moreover, our technique is scalable in the sense that even when running large instances of the multiple-choice knapsack problems, we can efficiently utilize the GPU compute resources and memory bandwidth to achieve significant speedups.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: