Optimization Online


Approximation of the Quadratic Knapsack Problem

Ulrich Pferschy(pferschy***at***uni-graz.at)
Joachim Schauer(joachim.schauer***at***uni-graz.at)

Abstract: 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 G = (V,E) whose vertices represent the knapsack items induces a quadratic profit p_ij for the items i and j whenever they are adjacent in G (i.e (i,j) are in E). 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. This result is shown by adopting a technique of Demaine et al. (2005). We also show strong NP-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 a 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.

Keywords: quadratic knapsack problem, special graph classes, approximation algorithm, book embedding, densest k-subgraph

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 12/04/2013
Entry Accepted: 12/17/2013
Entry Last Modified: 12/04/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society