Approximation of the quadratic knapsack problem

DOI10.1016/J.ORL.2016.05.005MaRDI QIDQ1694783zbMATH OpenOpenAlexFDO

Authors Peng Zhang

Publication date 6 February 2018

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

Full work available at URL https://arxiv.org/abs/1509.01866

zbMATH Keywords

approximation algorithmquadratic knapsack

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: For any given $epsilon>0$ we provide an algorithm for the Quadratic Knapsack Problem that has an approximation ratio within $O(n^{2/5+epsilon})$ and a run time within $O(n^{9/epsilon})$.

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• Approximation of the quadratic knapsack problem
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• The dense \(k\)-subgraph problem
• The quadratic 0-1 knapsack problem with series-parallel support
• The quadratic knapsack problem -- a survey

Cited in

(14)

• A lifted-space dynamic programming algorithm for the quadratic knapsack problem
• Variable fixing method by weighted average for the continuous quadratic knapsack problem
• A note on optimal solutions to quadratic knapsack problems
• Approximating single- and multi-objective nonlinear sum and product knapsack problems
• On the rectangular knapsack problem
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Lagrangian heuristics for the quadratic knapsack problem
• Quadratic bottleneck knapsack problems
• A Newton's method for the continuous quadratic knapsack problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• The quadratic knapsack problem -- a survey
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
• Adaptive feasible and infeasible evolutionary search for the knapsack problem with forfeits

This page was built for publication: Approximation of the quadratic knapsack problem

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