Asymptotic behavior of the quadratic knapsack problem

DOI10.1016/J.EJOR.2016.06.013zbMATH Open1346.90718OpenAlexW2415059730MaRDI QIDQ323537FDOQ323537

Authors: Joachim Schauer 

Publication date: 7 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.06.013

Recommendations

• A dynamic programming heuristic for the quadratic knapsack problem
• Exact Solution of the Quadratic Knapsack Problem
• Quadratic bottleneck knapsack problems
• An effective GRASP and tabu search for the 0-1 quadratic knapsack problem
• An experimental study of random knapsack problems

zbMATH Keywords

asymptotic analysisquadratic knapsack problemrandom instances

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The quadratic knapsack problem -- a survey
• Asymptotic Statistics
• Relations between average case complexity and approximation complexity
• Title not available (Why is that?)
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Quadratic knapsack problems
• Title not available (Why is that?)
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• On linear programs with random costs
• Probabilistic asymptotic properties of some combinatorial optimization problems
• A semidefinite programming approach to the quadratic knapsack problem
• Reoptimization in Lagrangian methods for the \(0\)-\(1\) 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
• Exact Solution of the Quadratic Knapsack Problem
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• An effective GRASP and tabu search for the 0-1 quadratic knapsack problem
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• Operations research and enterprise systems. Third international conference, ICORES 2014, Angers, France, March 6--8, 2014. Revised selected papers

Cited In (5)

• Optimal setup of a multihead weighing machine
• A cut-and-branch algorithm for the quadratic knapsack problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• A lifted-space dynamic programming algorithm for the quadratic knapsack problem
• A nonlinear multidimensional knapsack problem in the optimal design of mixture experiments

Uses Software

• Knapsack

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

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