The quadratic knapsack problem -- a survey
DOI10.1016/j.dam.2006.08.007zbMath1143.90028OpenAlexW2082782506WikidataQ58826435 ScholiaQ58826435MaRDI QIDQ875597
Publication date: 13 April 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.08.007
upper boundssemidefinite programmingvalid inequalitiesapproximation algorithmsquadratic knapsack problem
Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Approximation algorithms (68W25)
Related Items (83)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An O(n) algorithm for quadratic knapsack problems
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Geometric algorithms and combinatorial optimization
- Linear programming for the \(0-1\) quadratic knapsack problem
- Lagrangean methods for the 0-1 quadratic knapsack problem
- An extended formulation approach to the edge-weighted maximal clique problem
- A cutting-plane approach to the edge-weighted maximal clique problem
- Min-cut clustering
- On the \(0/1\) knapsack polytope
- The quadratic assignment problem. Theory and algorithms
- A semidefinite programming approach to the quadratic knapsack problem
- A new upper bound for the 0-1 quadratic knapsack problem
- Formulations and valid inequalities of the node capacitated graph partitioning problem
- The cut polytope and the Boolean quadric polytope
- The quadratic 0-1 knapsack problem with series-parallel support
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- Quadratic knapsack problems
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Approximations of pseudo-Boolean functions; applications to game theory
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Technical Note—A Note on Zero-One Programming
- Facets of the knapsack polytope
- Minimum cuts and related problems
- Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
- A Minimal Algorithm for the 0-1 Knapsack Problem
- Exact Solution of the Quadratic Knapsack Problem
- A Spectral Bundle Method for Semidefinite Programming
- Quadratic knapsack relaxations using cutting planes and semidefinite programming
- A Fast Parametric Maximum Flow Algorithm and Applications
- A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
- A Selection Problem of Shared Fixed Costs and Network Flows
- The traveling-salesman problem and minimum spanning trees: Part II
- Handbook of semidefinite programming. Theory, algorithms, and applications
This page was built for publication: The quadratic knapsack problem -- a survey