Asymptotic behavior of the quadratic knapsack problem

DOI10.1016/J.EJOR.2016.06.013zbMath1346.90718OpenAlexW2415059730MaRDI QIDQ323537

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

zbMATH Keywords

asymptotic analysisquadratic knapsack problemrandom instances

Mathematics Subject Classification ID

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

Related Items (5)

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

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The quadratic knapsack problem -- a survey
• Operations research and enterprise systems. Third international conference, ICORES 2014, Angers, France, March 6--8, 2014. Revised selected papers
• Probabilistic asymptotic properties of some combinatorial optimization problems
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• 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
• Detecting high log-densities
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
• Relations between average case complexity and approximation complexity
• On linear programs with random costs
• Quadratic knapsack problems
• Asymptotic Statistics
• Exact Solution of the Quadratic Knapsack Problem
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

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