Quadratic bottleneck knapsack problems

Ruonan Zhang, Abraham P. Punnen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


In this paper we study the quadratic bottleneck knapsack problem (QBKP) from an algorithmic point of view. QBKP is shown to be NP-hard and it does not admit polynomial time Ïμ-approximation algorithms for any Ïμ>0 (unless P=NP). We then provide exact and heuristic algorithms to solve the problem and also identify polynomially solvable special cases. Results of extensive computational experiments are reported which show that our algorithms can solve QBKP of reasonably large size and produce good quality solutions very quickly. Several variations of QBKP are also discussed.

Original languageEnglish
Pages (from-to)573-589
Number of pages17
JournalJournal of Heuristics
Issue number4
Publication statusPublished - Aug 2013
Externally publishedYes


  • Bottleneck
  • Knapsack problem
  • Quadratic
  • Quadratic threshold
  • Semi-greedy

Cite this