Quadratic bottleneck problems

Quadratic bottleneck problems

0.00 Avg rating0 Votes
Article ID: iaor201112736
Volume: 58
Issue: 2
Start Page Number: 153
End Page Number: 164
Publication Date: Mar 2011
Journal: Naval Research Logistics (NRL)
Authors: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.