The quadratic 0-1 knapsack problem with series-parallel support

DOI10.1016/S0167-6377(02)00122-0zbMath1010.90067OpenAlexW2164056371MaRDI QIDQ1866980

David J. jun. Rader, Gerhard J. Woeginger

Publication date: 2 April 2003

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(02)00122-0

zbMATH Keywords

computational complexitydynamic programmingknapsack problemapproximation schemeapproximability

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39) Complexity and performance of numerical algorithms (65Y20)

Related Items (27)

Quadratic bottleneck knapsack problems ⋮ Packing Under Convex Quadratic Constraints ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Asymptotic behavior of the quadratic knapsack problem ⋮ Approximation of the Quadratic Knapsack Problem ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ On the rectangular knapsack problem ⋮ The quadratic knapsack problem -- a survey ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ A lifted-space dynamic programming algorithm for the quadratic knapsack problem ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Approximation of the quadratic knapsack problem ⋮ The densest \(k\)-subgraph problem on clique graphs ⋮ A Dynamic Programming Heuristic for the Quadratic Knapsack Problem ⋮ LAD models, trees, and an analog of the fundamental theorem of arithmetic ⋮ Online maximum \(k\)-coverage ⋮ On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem ⋮ Global optimality conditions and optimization methods for quadratic knapsack problems ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs ⋮ Approximability issues for unconstrained and constrained maximization of half-product related functions ⋮ Approximation schemes for \(r\)-weighted minimization knapsack problems ⋮ Online Maximum k-Coverage ⋮ A PTAS for a class of binary non-linear programs with low-rank functions ⋮ Exact Solution Methods for the k-Item Quadratic Knapsack Problem ⋮ An approximate dynamic programming approach to convex quadratic knapsack problems ⋮ Packing under convex quadratic constraints

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Linear programming for the \(0-1\) quadratic knapsack problem
• Lagrangean methods for the 0-1 quadratic knapsack problem
• Min-cut clustering
• A new upper bound for the 0-1 quadratic knapsack problem
• On the supermodular knapsack problem
• Topology of series-parallel networks
• Fast Approximation Algorithms for Knapsack Problems
• Quadratic knapsack problems
• The Recognition of Series Parallel Digraphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• Exact Solution of the Quadratic Knapsack Problem
• Quadratic knapsack relaxations using cutting planes and semidefinite programming

This page was built for publication: The quadratic 0-1 knapsack problem with series-parallel support