Repository logo
 

Revisiting sparse dynamic programming for the 0/1 Knapsack Problem

Simple item page
dc.contributor.authorSifat, Tarequl Islam, author
dc.contributor.authorRajopadhye, Sanjay, advisor
dc.contributor.authorPouchet, Louis Noel, committee member
dc.contributor.authorBetten, Anton, committee member
dc.date.accessioned2019-06-14T17:06:21Z
dc.date.available2019-06-14T17:06:21Z
dc.date.issued2019
dc.description.abstractThe 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.
dc.format.mediumborn digital
dc.format.mediummasters theses
dc.identifierSifat_colostate_0053N_15373.pdf
dc.identifier.urihttps://hdl.handle.net/10217/195332
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.subjectdynamic programming
dc.subjectsparsity
dc.subjectsalable parallelization
dc.subject0/1 knapsack
dc.titleRevisiting sparse dynamic programming for the 0/1 Knapsack Problem
dc.typeText
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineComputer Science
thesis.degree.grantorColorado State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science (M.S.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Sifat_colostate_0053N_15373.pdf
Size:
515.43 KB
Format:
Adobe Portable Document Format
Download

Collections

2000-2019
Theses and Dissertations