Quadratic bottleneck problems

Abraham P. Punnen, Ruonan Zhang

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


We study the quadratic bottleneck problem (QBP) which generalizes several well-studied optimization problems. A weak duality theorem is introduced along with a general purpose algorithm to solve QBP. An example is given which illustrates duality gap in the weak duality theorem. It is shown that the special case of QBP where feasible solutions are subsets of a finite set having the same cardinality is NP-hard. Likewise the quadratic bottleneck spanning tree problem (QBST) is shown to be NP-hard on a bipartite graph even if the cost function takes 0-1 values only. Two lower bounds for QBST are derived and compared. Efficient heuristic algorithms are presented for QBST along with computational results. When the cost function is decomposable, we show that QBP is solvable in polynomial time whenever an associated linear bottleneck problem can be solved in polynomial time. As a consequence, QBP with feasible solutions form spanning trees, s-t paths, matchings, etc., of a graph are solvable in polynomial time with a decomposable cost function. We also show that QBP can be formulated as a quadratic minsum problem and establish some asymptotic results.

Original languageEnglish
Pages (from-to)153-164
Number of pages12
JournalNaval Research Logistics
Issue number2
Publication statusPublished - Mar 2011
Externally publishedYes


  • bottleneck extrema
  • bottleneck problems
  • combinatorial optimization
  • quadratic optimization

Cite this