Approximating the quadratic knapsack problem on special graph classes

DOI10.1007/978-3-319-08001-7_6MaRDI QIDQ3188866zbMATH OpenOpenAlexFDO

Authors 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

\(H\)-minor freeapproximation algorithmdensest \(k\)-subgraphquadratic knapsack problem

Mathematics Subject Classification ID

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

Recommendations

• Approximation of the quadratic knapsack problem
• The quadratic 0-1 knapsack problem with series-parallel support
• A cut-and-branch algorithm for the quadratic knapsack problem
• Approximation of knapsack problems with conflict and forcing graphs
• Quadratic bottleneck knapsack problems

Cited in

(5)

• Approximation of knapsack problems with conflict and forcing graphs
• Approximation schemes for \(r\)-weighted minimization knapsack problems
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Approximation of the quadratic knapsack problem
• scientific article; zbMATH DE number 4112385 (Why is no real title available?)

This page was built for publication: Approximating the quadratic knapsack problem on special graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188866)