You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Approximation of the Quadratic Knapsack Problem
Contributor:
Pferschy, Ulrich;
Schauer, Joachim
Published:
Institute for Operations Research and the Management Sciences (INFORMS), 2016
Published in:
INFORMS Journal on Computing, 28 (2016) 2, Seite 308-318
Language:
English
DOI:
10.1287/ijoc.2015.0678
ISSN:
1091-9856;
1526-5528
Origination:
Footnote:
Description:
We study the approximability of the classical quadratic knapsack problem (QKP) on special graph classes. In this case the quadratic terms of the objective function are not given for each pair of knapsack items. Instead, an edge weighted graph, whose vertices represent the knapsack items, induces a quadratic profit for every pair of items, which is adjacent in the graph. We show that the problem permits an FPTAS on graphs of bounded treewidth and a PTAS on planar graphs and more generally on H-minor free graphs. We also show strong 𝒩𝒫-hardness of QKP on graphs that are 3-book embeddable, a natural graph class that is related to planar graphs. In addition, we will argue that the problem is likely to have bad approximability behaviour on all graph classes that include the complete graph or contain large cliques. These hardness of approximation results under certain complexity assumptions carry over from the densest k-subgraph problem.