Approximating the product knapsack problem

Ulrich Pferschy; Joachim Schauer; Clemens Thielen

doi:10.1007/s11590-021-01760-x

Approximating the product knapsack problem

Ulrich Pferschy, Joachim Schauer, Clemens Thielen

Default

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

We consider the product knapsack problem, which is the variant of the classical 0-1 knapsack problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We present the first fully polynomial-time approximation scheme for the product knapsack problem, which is known to be weakly NP-hard. Moreover, we analyze the approximation quality achieved by a natural extension of the classical knapsack greedy procedure to the product knapsack problem.

Original language	English
Pages (from-to)	2529-2540
Number of pages	12
Journal	Optimization Letters
Volume	15
Issue number	8
DOIs	https://doi.org/10.1007/s11590-021-01760-x
State	Published - Nov 2021

Keywords

Approximation scheme
Greedy procedure
Knapsack problem

Access to Document

10.1007/s11590-021-01760-x

Cite this

@article{31707b5dae2b42d18464657fa20aac4a,

title = "Approximating the product knapsack problem",

abstract = "We consider the product knapsack problem, which is the variant of the classical 0-1 knapsack problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We present the first fully polynomial-time approximation scheme for the product knapsack problem, which is known to be weakly NP-hard. Moreover, we analyze the approximation quality achieved by a natural extension of the classical knapsack greedy procedure to the product knapsack problem.",

keywords = "Approximation scheme, Greedy procedure, Knapsack problem",

author = "Ulrich Pferschy and Joachim Schauer and Clemens Thielen",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s).",

year = "2021",

month = nov,

doi = "10.1007/s11590-021-01760-x",

language = "English",

volume = "15",

pages = "2529--2540",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "8",

}

TY - JOUR

T1 - Approximating the product knapsack problem

AU - Pferschy, Ulrich

AU - Schauer, Joachim

AU - Thielen, Clemens

PY - 2021/11

Y1 - 2021/11

N2 - We consider the product knapsack problem, which is the variant of the classical 0-1 knapsack problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We present the first fully polynomial-time approximation scheme for the product knapsack problem, which is known to be weakly NP-hard. Moreover, we analyze the approximation quality achieved by a natural extension of the classical knapsack greedy procedure to the product knapsack problem.

AB - We consider the product knapsack problem, which is the variant of the classical 0-1 knapsack problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We present the first fully polynomial-time approximation scheme for the product knapsack problem, which is known to be weakly NP-hard. Moreover, we analyze the approximation quality achieved by a natural extension of the classical knapsack greedy procedure to the product knapsack problem.

KW - Approximation scheme

KW - Greedy procedure

KW - Knapsack problem

UR - http://www.scopus.com/inward/record.url?scp=85107204338&partnerID=8YFLogxK

U2 - 10.1007/s11590-021-01760-x

DO - 10.1007/s11590-021-01760-x

M3 - Article

AN - SCOPUS:85107204338

SN - 1862-4472

VL - 15

SP - 2529

EP - 2540

JO - Optimization Letters

JF - Optimization Letters

IS - 8

ER -

Approximating the product knapsack problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this