Approximation of the Quadratic Knapsack Problem

DOI10.1287/ijoc.2015.0678zbMath1343.90080OpenAlexW2181448879MaRDI QIDQ3186661

Joachim Schauer, Ulrich Pferschy

Publication date: 12 August 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/57c11470a246ec2af5fb2060b7e148ef69018ff8

zbMATH Keywords

approximation algorithmbook embeddingquadratic knapsack problemspecial graph classesdensest \(k\)-subgraph

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Packing Under Convex Quadratic Constraints ⋮ A simple and fast algorithm for convex decomposition in relax-and-round mechanisms ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ On the rectangular knapsack problem ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ A lifted-space dynamic programming algorithm for the quadratic knapsack problem ⋮ Approximating single- and multi-objective nonlinear sum and product knapsack problems ⋮ Approximation of the quadratic knapsack problem ⋮ On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem ⋮ Packing under convex quadratic constraints

Cites Work

• Unnamed Item
• PTAS for densest \(k\)-subgraph in interval graphs
• A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
• The quadratic knapsack problem -- a survey
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Graphs with small book thickness
• Clustering and domination in perfect graphs
• Embedding planar graphs in four pages
• The book thickness of a graph
• A partial k-arboretum of graphs with bounded treewidth
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• On simple characterizations of k-trees
• The quadratic 0-1 knapsack problem with series-parallel support
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Approximating clique-width and branch-width
• Detecting high log-densities
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
• Densest k-Subgraph Approximation on Intersection Graphs
• The Knapsack Problem with Conflict Graphs
• Approximating the Quadratic Knapsack Problem on Special Graph Classes
• Graph minor theory
• Relations between average case complexity and approximation complexity
• Approximation algorithms for NP-complete problems on planar graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem
• Hard tiling problems with simple tiles

This page was built for publication: Approximation of the Quadratic Knapsack Problem