Encyclopedia

Linear bottleneck assignment problem

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated December 8, 2025

In combinatorial optimization, a field within mathematics, the linear bottleneck assignment problem (LBAP) is similar to the linear assignment problem.

In plain words the problem is stated as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the maximum cost among the individual assignments is minimized.

The term "bottleneck" is explained by a common type of application of the problem, where the cost is the duration of the task performed by an agent. In this setting the "maximum cost" is "maximum duration", which is the bottleneck for the schedule of the overall job, to be minimized.

01Formal definition

The formal definition of the bottleneck assignment problem is

Given two sets, A and T, together with a weight function C : A × T → R. Find a bijection f : A → T such that the cost function:

$\max _{a\in A}C(a,f(a))$

is minimized.

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:

$\max _{a\in A}C_{a,f(a)}$

02Asymptotics

Let $c_{n}^{*}$ denote the optimal objective function value for the problem with n agents and n tasks. If the costs $c_{ij}$ are sampled from the uniform distribution on (0,1), then

$E[c_{n}^{*}]={\frac {\log n+\log 2+\gamma }{n}}+O\left({\frac {(\log n)^{2}}{n^{7/5}}}\right)$

and

$Var[c_{n}^{*}]={\frac {\zeta (2)-2(\log 2)^{2}}{n^{2}}}+O\left({\frac {(\log n)^{2}}{n^{7/3}}}\right).$

Watch videos about Linear bottleneck assignment problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Linear bottleneck assignment problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.