Quadratic bottleneck assignment problem
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, the quadratic bottleneck assignment problem (QBAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research, from the category of the facilities location problems. It is related to the quadratic assignment problem in the same way as the linear bottleneck assignment problem is related to the linear assignment problem, the "sum" is replaced with "max" in the objective function.
The problem models the following real-life problem: :There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g., the amount of supplies transported between the two facilities).
The problem is to assign all facilities to different locations with the goal of minimizing the maximum of the distances multiplied by the corresponding flows.
In mathematics, the quadratic bottleneck assignment problem (QBAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research, from the category of the facilities location problems. It is related to the quadratic assignment problem in the same way as the linear bottleneck assignment problem is related to the linear assignment problem, the "sum" is replaced with "max" in the objective function.
The problem models the following real-life problem: There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g., the amount of supplies transported between the two facilities).
The problem is to assign all facilities to different locations with the goal of minimizing the maximum of the distances multiplied by the corresponding flows.
Computational complexity
The problem is NP-hard, as it can be used to formulate the Hamiltonian cycle problem by using flows in the pattern of a cycle and distances that are short for graph edges and long for non-edges.
Special cases
Bottleneck traveling salesman problem Graph bandwidth problem
Text derived from https://en.wikipedia.org/w/index.php?oldid=1301120325 under CC BY-SA 4.0; modifications have been made.