In mathematics, the quadratic bottleneck assignment problem (QBAP) is one of fundamental

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...

problems in the branch of

optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve dec ...

, from the category of the

facilities location The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering fac ...

problems. It is related to the

quadratic assignment problem The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by ...

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 In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...

. 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 In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

, as it can be used to formulate the

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

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 In graph theory, the graph bandwidth problem is to label the vertices of a graph with distinct integers so that the quantity \max\ is minimized ( is the edge set of ). The problem may be visualized as placing the vertices of a graph at distin ...

References

{{reflist NP-hard problems Combinatorial optimization