Approximating the Quadratic Knapsack Problem on Special Graph Classes

DOI10.1007/978-3-319-08001-7_6zbMath1417.68163OpenAlexW968734414MaRDI QIDQ3188866

Ulrich Pferschy, Joachim Schauer

Publication date: 2 September 2014

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-08001-7_6

zbMATH Keywords

approximation algorithmquadratic knapsack problemdensest \(k\)-subgraph\(H\)-minor free

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Approximation of the Quadratic Knapsack Problem ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ Approximation schemes for \(r\)-weighted minimization knapsack problems

This page was built for publication: Approximating the Quadratic Knapsack Problem on Special Graph Classes