A Fast and Effective Breakpoints Heuristic Algorithm for the Quadratic Knapsack Problem

Dorit S. Hochbaum, Philipp Baumann, Olivier Goldschmidt +1

The Quadratic Knapsack Problem (QKP) involves selecting a subset of elements that maximizes the sum of pairwise and singleton utilities without exceeding a given budget. The pairwi…