• Home
  • Advanced Search
  • Directory of Libraries
  • About lib.ir
  • Contact Us
  • History

عنوان
Revisiting Sparse Dynamic Programming for the 0/1 Knapsack Problem

پدید آورنده
Sifat, Tarequl Islam

موضوع
Computer science

رده

کتابخانه
Center and Library of Islamic Studies in European Languages

محل استقرار
استان: Qom ـ شهر: Qom

Center and Library of Islamic Studies in European Languages

تماس با کتابخانه : 32910706-025

NATIONAL BIBLIOGRAPHY NUMBER

Number
TLpq2268337630

LANGUAGE OF THE ITEM

.Language of Text, Soundtrack etc
انگلیسی

TITLE AND STATEMENT OF RESPONSIBILITY

Title Proper
Revisiting Sparse Dynamic Programming for the 0/1 Knapsack Problem
General Material Designation
[Thesis]
First Statement of Responsibility
Sifat, Tarequl Islam
Subsequent Statement of Responsibility
Rajopadhye, Sanjay

.PUBLICATION, DISTRIBUTION, ETC

Name of Publisher, Distributor, etc.
Colorado State University
Date of Publication, Distribution, etc.
2019

PHYSICAL DESCRIPTION

Specific Material Designation and Extent of Item
42

DISSERTATION (THESIS) NOTE

Dissertation or thesis details and type of degree
M.S.
Body granting the degree
Colorado State University
Text preceding or following the note
2019

SUMMARY OR ABSTRACT

Text of Note
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.

TOPICAL NAME USED AS SUBJECT

Computer science

PERSONAL NAME - PRIMARY RESPONSIBILITY

Rajopadhye, Sanjay
Sifat, Tarequl Islam

ELECTRONIC LOCATION AND ACCESS

Electronic name
 مطالعه متن کتاب 

p

[Thesis]
276903

a
Y

Proposal/Bug Report

Warning! Enter The Information Carefully
Send Cancel
This website is managed by Dar Al-Hadith Scientific-Cultural Institute and Computer Research Center of Islamic Sciences (also known as Noor)
Libraries are responsible for the validity of information, and the spiritual rights of information are reserved for them
Best Searcher - The 5th Digital Media Festival