التفاصيل البيبلوغرافية
| العنوان: |
Positional Knapsack Problem: NP-hardness and approximation scheme (Brief Announcement). |
| المؤلفون: |
Pedrosa, Lehilton L.C., da Silva, Mauro R.C., Schouery, Rafael C.S. |
| المصدر: |
Procedia Computer Science; 2023, Vol. 223, p400-402, 3p |
| مصطلحات موضوعية: |
KNAPSACK problems, NP-hard problems, DYNAMIC programming, APPROXIMATION algorithms, ALGORITHMS |
| مستخلص: |
We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position. [ABSTRACT FROM AUTHOR] |
|
Copyright of Procedia Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Supplemental Index |
Full Text Finder