A lifted-space dynamic programming algorithm for the quadratic knapsack problem

DOI10.1016/J.DAM.2023.02.003zbMATH Open1519.90203OpenAlexW3175250543MaRDI QIDQ6041830FDOQ6041830

Authors: Franklin Djeumou Fomeni 

Publication date: 15 May 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2023.02.003

Recommendations

• A dynamic programming heuristic for the quadratic knapsack problem
• A cut-and-branch algorithm for the quadratic knapsack problem
• New algorithm for quadratic integer knapsack problems
• Exact Solution of the Quadratic Knapsack Problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem

zbMATH Keywords

dynamic programminglocal searchinteger programmingknapsack problemsbinary quadratic optimization

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The quadratic knapsack problem -- a survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Title not available (Why is that?)
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Sequence independent lifting in mixed integer programming
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Quadratic knapsack problems
• An Algorithm for Large Zero-One Knapsack Problems
• A semidefinite programming approach to the quadratic knapsack problem
• The quadratic 0-1 knapsack problem with series-parallel support
• Solution of large quadratic knapsack problems through aggressive reduction
• A dynamic programming heuristic for the quadratic knapsack problem
• Asymptotic behavior of the quadratic knapsack problem
• Exact Solution of the Quadratic Knapsack Problem
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• Linear programming for the \(0-1\) quadratic knapsack problem
• Title not available (Why is that?)
• Approximation of the quadratic knapsack problem
• Approximation of the quadratic knapsack problem
• Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Title not available (Why is that?)
• Lagrangian heuristics for the quadratic knapsack problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Parametric convex quadratic relaxation of the quadratic knapsack problem
• 0-1 quadratic knapsack problem solved with VNS algorithm
• A cut-and-branch algorithm for the quadratic knapsack problem

Cited In (7)

• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• Lagrangian heuristics for the quadratic knapsack problem
• A cut-and-branch algorithm for the quadratic knapsack problem
• A logarithmic descent direction algorithm for the quadratic knapsack problem
• New algorithm for quadratic integer knapsack problems
• A dynamic programming heuristic for the quadratic knapsack problem
• An approximate dynamic programming approach to convex quadratic knapsack problems

This page was built for publication: A lifted-space dynamic programming algorithm for the quadratic knapsack problem

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