Loading...
Please wait, while we are loading the content...
A scalable gpu-based approach to accelerate the multiple-choice knapsack problem.
| Content Provider | CiteSeerX |
|---|---|
| Author | Suri, Bharath Bordoloi, Unmesh D. Eles, Petru |
| Abstract | Abstract—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. I. |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |
