عنوان

Revisiting Sparse Dynamic Programming for the 0/1 Knapsack Problem

شماره

TLpq2268337630

زبان متن نوشتاري يا گفتاري و مانند آن

انگلیسی

عنوان اصلي

Revisiting Sparse Dynamic Programming for the 0/1 Knapsack Problem

نام عام مواد

[Thesis]

نام نخستين پديدآور

Sifat, Tarequl Islam

نام ساير پديدآوران

Rajopadhye, Sanjay

نام ناشر، پخش کننده و غيره

Colorado State University

تاریخ نشرو بخش و غیره

2019

نام خاص و کميت اثر

42

جزئيات پايان نامه و نوع درجه آن

M.S.

کسي که مدرک را اعطا کرده

Colorado State University

امتياز متن

2019

متن يادداشت

The 0/1-Knapsack Problem is a classic NP-hard problem. There are two common approaches to obtain the exact solution: branch-and-bound (BB) and dynamic programming (DP). A socalled, "sparse" DP algorithm (SKPDP) that performs fewer operations than the standard algorithm (KPDP) is well known. To the best of our knowledge, there has been no quantitative analysis of the benefits of sparsity. We provide a careful empirical evaluation of SKPDP and observe that for a "large enough" capacity, C, the number of operations performed by SKPDP is invariant with respect to C for many problem instances. This leads to the possibility of an exponential improvement over the conventional KPDP. We experimentally explore SKPDP over a large range of knapsack problem instances and provide a detailed study of the attributes that impact the performance. DP algorithms have a nice regular structure and are amenable to highly parallel implementations. However, due to the dependence structure, parallelizing SKPDP is challenging. We propose two parallelization strategies (fine-grain and coarse-grain) for SKPDP on modern multi-core processors and demonstrate a scalable improvement in the performance.

موضوع مستند نشده

Computer science

مستند نام اشخاص تاييد نشده

Rajopadhye, Sanjay

مستند نام اشخاص تاييد نشده

Sifat, Tarequl Islam

نام الکترونيکي

فرمت انتشار

p

نوع ماده

[Thesis]

کد کاربرگه

276903

سطح دسترسي

a

تكميل شده

Y