Approximation issues of fractional knapsack with penalties: a note

Sergey Kovalev ()
Additional contact information
Sergey Kovalev: INSEEC U. Research Center

4OR, 2022, vol. 20, issue 2, No 2, 209-216

Abstract: Abstract Malaguti et al. introduce (Eur J Oper Res 273:874–888, 2019) the Fractional Knapsack Problem with Penalties, which is similar to the classical 0-1 Knapsack problem, except that each of the n variables associated with one of the n items can take any value from the interval [0, 1], and values other than 0 and 1 are penalized. They state that the problem is NP-hard in the ordinary sense as a generalization of the classical 0-1 knapsack problem and develop a fully polynomial-time approximation scheme for the case of non-negative non-decreasing profit functions. It is demonstrated that, unless $$\mathcal P=NP$$ P = N P , no polynomial-time approximation algorithm with any approximation ratio exists for the case of polynomially defined, polynomially computable, discontinuous and non-monotone penalty functions even if there is a single item. A fully polynomial-time approximation scheme which is roughly n times faster than the one of Malaguti et al. for the same case is also presented.

Keywords: Knapsack problem; Computational complexity; Fully polynomial-time approximation scheme; 90–10 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-021-00474-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:20:y:2022:i:2:d:10.1007_s10288-021-00474-1

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-021-00474-1

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().