Linear assignment problem in bottlenecks

In combinatorial optimization , the linear bottleneck assignment problem , LBAP is a linear assignment problem , similar to the assignment problem ^[1] .

In simple words, the task is set as follows:

There are a number of performers and a number of works . Any performer can perform any work, the implementation of which can cost some price , which depends on the appointment of the performer-work. It is required to perform all the work in appointing exactly one performer for each work in such a way as to minimize the maximum price encountered during appointments.

The term " bottleneck " is explained in the usual way of using a task when the price is taken as the duration of the work done by the performer. Under these conditions, the "maximum price" becomes the "maximum duration", which is a bottleneck when planning a full job, and this maximum duration should be made as small as possible.

The linear bottleneck assignment problem was first described by Fulkerson, Glicksberg and Gross in a paper dedicated to the distribution of work among machines in order to minimize lead times ^[2] .

Formal definition

The formal definition of a bottleneck assignment problem is as follows:

Two sets, A and T , are specified , together with the 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))

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

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

is minimal.

Usually, the weight function is defined as a square real matrix C , so the cost function can be written as follows:

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

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

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

Problem formulation as a math programming problem

\min \,\max _{i,j}c_{i,j}x_{i,j}

{\ displaystyle \ min \, \ max _ {i, j} c_ {i, j} x_ {i, j}}

\min \,\max _{i,j}c_{i,j}x_{i,j}

under conditions:

\sum _{j=1}^{n}x_{i,j}=1\ (i=1,2,\dots ,n),

{\ displaystyle \ sum _ {j = 1} ^ {n} x_ {i, j} = 1 \ (i = 1,2, \ dots, n),}

\sum _{i=1}^{n}x_{i,j}=1\ (j=1,2,\dots ,n),

{\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i, j} = 1 \ (j = 1,2, \ dots, n),}

x_{i,j}\in \{0,1\}\ (i,j=1,2,\dots ,n)

{\ displaystyle x_ {i, j} \ in \ {0,1 \} \ (i, j = 1,2, \ dots, n)}

Solution Methods

The following lemma is useful for solving the problem:

Lemma. ^[1] Let $C=(c_{i,j})$ ${\ displaystyle C = (c_ {i, j})}$ - task price matrix, Then

1. The optimal value of the problem is determined by one of the elements of the matrix.

c_{i,j}

{\ displaystyle c_ {i, j}}

.

2. The optimal solution depends only on the relative order of the elements of the matrix, and not on their numerical values.

Example. Let the matrix be given

$C={\begin{pmatrix}\pi &{\sqrt {3}}&54392\\0&e^{3}&e^{3}\\{-}2&\sin {(\pi /8)}&4\\\end{pmatrix}}$ ${\ displaystyle C = {\ begin {pmatrix} \ pi & {\ sqrt {3}} & 54392 \\ 0 & e ^ {3} & e ^ {3} \\ {-} 2 & \ sin {(\ pi / 8)} & 4 \\\ end {pmatrix}}}$

Arrange the elements of the matrix $-2<0<\sin {(\pi /8)}<{\sqrt {3}}<\pi <4<e^{3}=e^{3}<54392$ ${\ displaystyle -2 <0 <\ sin {(\ pi / 8)} <{\ sqrt {3}} <\ pi <4 <e ^ {3} = e ^ {3} <54392}$ .

Replace the smallest element −2 with 0, followed by 0 replace with 1, then $\sin {(\pi /8)}$ ${\ displaystyle \ sin {(\ pi / 8)}}$ replace with 2 and so on. We get the following matrix: $C'={\begin{pmatrix}4&3&7\\1&6&6\\0&2&5\\\end{pmatrix}}$ ${\ displaystyle C '= {\ begin {pmatrix} 4 & 3 & 7 \\ 1 & 6 & 6 \\ 0 & 2 & 5 \\\ end {pmatrix}}}$ .

The optimal solution to the problem is a permutation {2, 1, 3} with the maximum value for the matrix $C^{'}$ ${\ displaystyle C '}$ 5, which corresponds to a value of 4 in the original matrix $C$ ${\ displaystyle C}$ .

Threshold algorithm

The idea of using the threshold value method belongs to Garfinkel ^[3] .

  Assign initial values  $t_{\min }=\min _{i,j}{c_{i,j}},t_{\max }=\max _{i,j}{c_{i,j}}$             $t$         $min$           $=$         $min$         $i$       $,$       $j$               $c$         $i$       $,$       $j$             $,$         $t$         $max$           $=$         $max$         $i$       $,$       $j$               $c$         $i$       $,$       $j$                 ${\ displaystyle t _ {\ min} = \ min _ {i, j} {c_ {i, j}}, t _ {\ max} = \ max _ {i, j} {c_ {i, j}}}$       .
 If a  $t_{\min }=t_{\max }$             $t$         $min$           $=$         $t$         $max$               ${\ displaystyle t _ {\ min} = t _ {\ max}}$       then
   optimal value =  $t_{\min }$             $t$         $min$               ${\ displaystyle t _ {\ min}}$       and any permutation {1, 2,.  .  .  , n} is optimal.
 Otherwise, 
   while there  $c_{i,j}:t_{\min }<c_{i,j}<t_{\max }$             $c$         $i$       $,$       $j$           $:$         $t$         $min$           $<$         $c$         $i$       $,$       $j$           $<$         $t$         $max$               ${\ displaystyle c_ {i, j}: t _ {\ min} <c_ {i, j} <t _ {\ max}}$       to execute
     Find the median , t numbers  $t_{\min }<c_{i,j}<t_{\max }$             $t$         $min$           $<$         $c$         $i$       $,$       $j$           $<$         $t$         $max$               ${\ displaystyle t _ {\ min} <c_ {i, j} <t _ {\ max}}$     
     Build a graph  $T$           $T$           ${\ displaystyle T}$     
     If a  $T$           $T$           ${\ displaystyle T}$       contains a perfect match then accept 
       $t_{\min }=t$             $t$         $min$           $=$       $t$           ${\ displaystyle t _ {\ min} = t}$     
     otherwise we accept 
       $t_{\max }=t$             $t$         $max$           $=$       $t$           ${\ displaystyle t _ {\ max} = t}$      
     end if
   end of cycle
   If checking the existence of a perfect match for  $t_{\min }$             $t$         $min$               ${\ displaystyle t _ {\ min}}$       was not executed, we will execute it.
   Build a graph  $T$           $T$           ${\ displaystyle T}$       for  $t_{\min }$             $t$         $min$               ${\ displaystyle t _ {\ min}}$     
   If a  $T$           $T$           ${\ displaystyle T}$       contains a perfect match, accept
     $t_{\max }=t_{\min }$             $t$         $max$           $=$         $t$         $min$               ${\ displaystyle t _ {\ max} = t _ {\ min}}$     
   end if
 end if

The optimal value will be

t_{\max }

{\ displaystyle t _ {\ max}}

, and the optimal solution can be found from the corresponding graph.

As you can see, at each step of the cycle the 'threshold algorithm' goes through two stages. In the first step, a 'threshold value' is selected. $t$ ${\ displaystyle t}$ and 'threshold matrix' $T$ ${\ displaystyle T}$ which is defined as follows:

T_{i,j}=

{\ displaystyle T_ {i, j} =}

1 if

c_{ij}>t

{\ displaystyle c_ {ij}> t}

0 otherwise.

At the second stage, it is checked whether the assignment with zero price exists (for the price matrix $T$ ${\ displaystyle T}$ ). To verify this, a bichromatic graph G = (U, V; E) with | U | = | V | = n and arcs $[i,j]\in E$ ${\ displaystyle [i, j] \ in E}$ then and only if $T_{i,j}=0$ ${\ displaystyle T_ {i, j} = 0}$ . (In other words, we must check whether the bipartite graph corresponding to the threshold matrix contains a perfect matching or not). Min threshold $t$ ${\ displaystyle t}$ for which the corresponding bichromatic graph contains a perfect matching is the optimal value of the problem. There are several ways to implement the threshold algorithm. One possibility is to use binary search in the first stage. This will lead to $O(M(n)\log(n))$ ${\ displaystyle O (M (n) \ log (n))}$ algorithm where $M(n)$ ${\ displaystyle M (n)}$ - time complexity of checking the existence of a perfect match. We can use Ibarra and Moran’s matrix algorithm ^[4] to find out if there is a perfect matching. Then the optimal solution can be found with bit complexity. $O(n^{\beta }\log ^{k}n)$ ${\ displaystyle O (n ^ {\ beta} \ log ^ {k} n)}$ . To multiply two n × n matrices you need $O(n^{\beta })$ ${\ displaystyle O (n ^ {\ beta})}$ arithmetic operations and k is an integer resulting from actions on long integers. Coppersmith and Grapes (Winograd) ^[5] showed that matrix multiplication can be done with $\beta =2{,}376$ ${\ displaystyle \ beta = 2 {,} 376}$ . If we want to obtain the corresponding optimal solution, we can use the method of Alt, Blum, Melhorn and Paula (Alt, Blum, Mehlhorn, Paul) ^[6] and we get the full complexity $O\left(n^{2{,}5}\left/{\sqrt {\log(n)}}\right.\right)$ ${\ displaystyle O \ left (n ^ {2 {,} 5} \ left / {\ sqrt {\ log (n)}} \ right. \ right)}$ in the case of a dense matrix. Here density means the number of nonzero elements $T_{i,j}$ ${\ displaystyle T_ {i, j}}$ matrix equals $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ .

This method is theoretically the best known method for solving a problem.

Dual Algorithm

Closely related to the threshold method is the following dual algorithm.

  Calculate  $t=\max _{k=1,2,\dots ,n}(\min _{r=1,2,\dots ,n}c_{r,k},\min _{j=1,2,\dots ,n}c_{k,j})$           $t$       $=$         $max$         $k$       $=$       $one$       $,$       $2$       $,$       $...$       $,$       $n$           $($         $min$         $r$       $=$       $one$       $,$       $2$       $,$       $...$       $,$       $n$             $c$         $r$       $,$       $k$           $,$         $min$         $j$       $=$       $one$       $,$       $2$       $,$       $...$       $,$       $n$             $c$         $k$       $,$       $j$           $)$           ${\ displaystyle t = \ max _ {k = 1,2, \ dots, n} (\ min _ {r = 1,2, \ dots, n} c_ {r, k}, \ min _ {j = 1 , 2, \ dots, n} c_ {k, j})}$     
 Set  $M=\varnothing$           $M$       $=$       $\emptyset$           ${\ displaystyle M = \ varnothing}$       (empty set).
 Bye | M |  <n, execute
   We define a bipartite graph G corresponding to the threshold value t.
   Find the maximum matching in G.
   If | M |  <n, then
     Let be  $R\subseteq U$           $R$       $\subseteq$       $U$           ${\ displaystyle R \ subseteq U}$       and  $J\subseteq V$           $J$       $\subseteq$       $V$           ${\ displaystyle J \ subseteq V}$       - sets of vertices in the minimal cover of the graph G.
     Set  $t=\min _{r\in R,j\in J}c_{r,j}$           $t$       $=$         $min$         $r$       $\in$       $R$       $,$       $j$       $\in$       $J$             $c$         $r$       $,$       $j$               ${\ displaystyle t = \ min _ {r \ in R, j \ in J} c_ {r, j}}$     
   end if
 end of cycle

The algorithm uses some information about the threshold value t, namely the fact that the optimal value cannot be less than the maximum value of the minimum elements in the rows, as well as the maximum value of the minimum elements in the columns of the matrix C. Thus, as the first threshold value can take

t=\max _{1\leqslant k\leqslant n}(\min _{1\leqslant r\leqslant n}c_{r,k},\min _{1\leqslant j\leqslant n}c_{k,j})

{\ displaystyle t = \ max _ {1 \ leqslant k \ leqslant n} (\ min _ {1 \ leqslant r \ leqslant n} c_ {r, k}, \ min _ {1 \ leqslant j \ leqslant n} c_ {k, j})}

The dual method starts with this value t and creates minimal sets (indices) of columns. $J$ ${\ displaystyle J}$ and strings $R$ ${\ displaystyle R}$ covering all elements of the matrix $c_{r,j}\leqslant t$ ${\ displaystyle c_ {r, j} \ leqslant t}$ . This can be done by finding the maximum set of arcs in the graph G, giving the matching. Here the graph G is a bipartite graph with arcs (r, j) for which $c_{r,j}\leqslant t$ ${\ displaystyle c_ {r, j} \ leqslant t}$ . If the matching does not contain all the rows and columns, there are matrix entries that define the optimal value, and these entries are greater than t. Because of this, we can adopt a new meaning. $t=\min _{r\in R,j\in J}c_{r,j}$ ${\ displaystyle t = \ min _ {r \ in R, j \ in J} c_ {r, j}}$ and build a new graph G. This graph contains all the edges of the previous graph and at least one new edge, so that we can start the search for the maximum matching with the one already found at the previous step. We continue until we find the perfect matching.

Algorithm of consecutive increments

Another approach to solving the problem can be the use of the ideas of the Hungarian method ^[7] . In Russia, this method is known as the Gross Algorithm. We present the method in the implementation of Deriggs and Zimmerman ^[8] .

We introduce several definitions.

A complementary matching path is a path containing a matching arc, and one of the two adjacent arcs necessarily belongs to the matching (i.e., the arcs are interspersed — there is an arc that does not belong to it, and vice versa) from the matching arc.

Let be $P=([i_{1},j_{1}],[i_{2},j_{1}],[i_{2},j_{2}],\dots ,[i_{k},j_{k}])$ ${\ displaystyle P = ([i_ {1}, j_ {1}], [i_ {2}, j_ {1}], [i_ {2}, j_ {2}], \ dots, [i_ {k} , j_ {k}])}$ - complementary path for the match M.

Bottleneck size $\ell (P)$ ${\ displaystyle \ ell (P)}$ defined as

\ell (P)=\max(c([i_{1},j_{1}]),c([i_{2},j_{2}]),\dots ,c([i_{k},j_{k}]))

{\ displaystyle \ ell (P) = \ max (c ([i_ {1}, j_ {1}]), c ([i_ {2}, j_ {2}]), \ dots, c ([i_ { k}, j_ {k}]))}

.

The complementary path is called the b-shortest path if the size of the bottleneck is minimal among all the complementary paths M.

  Let be  $G=(U,V;E)$           $G$       $=$       $($       $U$       $,$       $V$       $;$       $E$       $)$           ${\ displaystyle G = (U, V; E)}$       - bichromatic graph with arc lengths  $c_{i,j}$             $c$         $i$       $,$       $j$               ${\ displaystyle c_ {i, j}}$       for arcs  $[i,j]\in E$           $[$       $i$       $,$       $j$       $]$       $\in$       $E$           ${\ displaystyle [i, j] \ in E}$     
 Find the lower bound t for the objective function
      (those.  $t=\max {(\max _{u\in U}\min _{v\in V}c_{u,v},\max _{v\in V}\min _{u\in U}c_{u},v)}$           $t$       $=$       $max$         $($         $max$         $u$       $\in$       $U$             $min$         $v$       $\in$       $V$             $c$         $u$       $,$       $v$           $,$         $max$         $v$       $\in$       $V$             $min$         $u$       $\in$       $U$             $c$         $u$           $,$       $v$       $)$             ${\ displaystyle t = \ max {(\ max _ {u \ in U} \ min _ {v \ in V} c_ {u, v}, \ max _ {v \ in V} \ min _ {u \ in U} c_ {u}, v)}}$       )
 Find the maximum matching of M in the graph G, having arcs [i, j] if  $c_{i,j}\leqslant t$             $c$         $i$       $,$       $j$           $⩽$       $t$           ${\ displaystyle c_ {i, j} \ leqslant t}$     
 if | M |  = | U |, then we obtained the optimal solution t with the optimal ratio M, and complete the work.
 end if
 Let L be the set of elements of U for which there is no matching.
 until L is empty, execute
   Pick vertex  $i\in L$           $i$       $\in$       $L$           ${\ displaystyle i \ in L}$     
   Set  $L=L\backslash \{i\}$           $L$       $=$       $L$       $∖$       ${$       $i$       $}$           ${\ displaystyle L = L \ backslash \ {i \}}$     
   P = Dijkstra (i)
   Comment: The function Dijkstra (i) returns a complementary path starting at vertex i
   If the path is not found, then
     Set  $M=M\ominus P$           $M$       $=$       $M$       $⊖$       $P$           ${\ displaystyle M = M \ ominus P}$     
     Set  $t=\max(t,\ell (P))$           $t$       $=$       $max$       $($       $t$       $,$       $ℓ$       $($       $P$       $)$       $)$           ${\ displaystyle t = \ max (t, \ ell (P))}$     
   end if
 end bye
 Comment: M is the maximum matching with the minimum price t.

The B-shortest complementary path is found in the Dijkstra () function.Mark the vertex during the search for the b-shortest path

x\in U

{\ displaystyle x \ in U}

by value

({\overline {\alpha }}(x),{\overline {\beta }}(x))

{\ displaystyle ({\ overline {\ alpha}} (x), {\ overline {\ beta}} (x))}

where

{\overline {\alpha }}(x)

{\ displaystyle {\ overline {\ alpha}} (x)}

is the size of the bottleneck b-shortest path of

i_{1}

{\ displaystyle i_ {1}}

to this peak as well

{\overline {\beta }}(x)

{\ displaystyle {\ overline {\ beta}} (x)}

means the immediate predecessor in the b-shortest path of

i_{1}

{\ displaystyle i_ {1}}

to the top

x

{\ displaystyle x}

.

Similarly, mark the top $x\in V$ ${\ displaystyle x \ in V}$ by value $(\alpha (x),\beta (x))$ ${\ displaystyle (\ alpha (x), \ beta (x))}$ where $\alpha (x)$ ${\ displaystyle \ alpha (x)}$ is the size of the bottleneck b-shortest path of $i_{1}$ ${\ displaystyle i_ {1}}$ to this peak as well $\beta (x)$ ${\ displaystyle \ beta (x)}$ means the immediate predecessor in the b-shortest path of $i_{1}$ ${\ displaystyle i_ {1}}$ to the top $x$ ${\ displaystyle x}$ .

  Dijkstra (i) function
 Comment: A modified Dijkstra algorithm for the assignment problem for bottlenecks.
 Mark all vertices  $j\in V$           $j$       $\in$       $V$           ${\ displaystyle j \ in V}$       by putting  $(\alpha (j),\beta (j))=(\infty ,\varnothing )$           $($       $α$       $($       $j$       $)$       $,$       $β$       $($       $j$       $)$       $)$       $=$       $($       $\infty$       $,$       $\emptyset$       $)$           ${\ displaystyle (\ alpha (j), \ beta (j)) = (\ infty, \ varnothing)}$       .
 Put R = V Comment: R contains unvisited vertices V
 α (i) = t, P = empty
 For all neighbors  $j\in R$           $j$       $\in$       $R$           ${\ displaystyle j \ in R}$       vertices i execute
   If a  $\alpha (j)>\max({\overline {\alpha }}(i),c_{i,j})$           $α$       $($       $j$       $)$       $>$       $max$       $($           $α$       $¯$           $($       $i$       $)$       $,$         $c$         $i$       $,$       $j$           $)$           ${\ displaystyle \ alpha (j)> \ max ({\ overline {\ alpha}} (i), c_ {i, j})}$       then
     Set  $\alpha (j)=\max({\overline {\alpha }}(i),c_{i,j})$           $α$       $($       $j$       $)$       $=$       $max$       $($           $α$       $¯$           $($       $i$       $)$       $,$         $c$         $i$       $,$       $j$           $)$           ${\ displaystyle \ alpha (j) = \ max ({\ overline {\ alpha}} (i), c_ {i, j})}$     
     $\beta (j)=i$           $β$       $($       $j$       $)$       $=$       $i$           ${\ displaystyle \ beta (j) = i}$     
   end if
 end of cycle
 while R is empty, perform
   Find the top  $r\in R$           $r$       $\in$       $R$           ${\ displaystyle r \ in R}$       with minimal  $\alpha (r)$           $α$       $($       $r$       $)$           ${\ displaystyle \ alpha (r)}$       ;
   If a  $\alpha (r)=\infty$           $α$       $($       $r$       $)$       $=$       $\infty$           ${\ displaystyle \ alpha (r) = \ infty}$       then 
     Set  $R=\varnothing$           $R$       $=$       $\emptyset$           ${\ displaystyle R = \ varnothing}$     
   otherwise
     if r is not part of the matching, then
       Find the path P formed by the sequence of vertices  $(i,\dots ,{\overline {\beta }}(\beta (r)),\beta (r),r)$           $($       $i$       $,$       $...$       $,$           $β$       $¯$           $($       $β$       $($       $r$       $)$       $)$       $,$       $β$       $($       $r$       $)$       $,$       $r$       $)$           ${\ displaystyle (i, \ dots, {\ overline {\ beta}} (\ beta (r)), \ beta (r), r)}$     
       Set  $\ell (P)=\alpha (r)$           $ℓ$       $($       $P$       $)$       $=$       $α$       $($       $r$       $)$           ${\ displaystyle \ ell (P) = \ alpha (r)}$     
       $R=\varnothing$           $R$       $=$       $\emptyset$           ${\ displaystyle R = \ varnothing}$     
     Otherwise
       Let [s, r] be a matching edge
       Mark s:  $({\overline {\alpha }}(s),{\overline {\beta }}(s))=(\alpha (r),r)$           $($           $α$       $¯$           $($       $s$       $)$       $,$           $β$       $¯$           $($       $s$       $)$       $)$       $=$       $($       $α$       $($       $r$       $)$       $,$       $r$       $)$           ${\ displaystyle ({\ overline {\ alpha}} (s), {\ overline {\ beta}} (s)) = (\ alpha (r), r)}$     
       Set  $R=R\backslash \{r\}$           $R$       $=$       $R$       $∖$       ${$       $r$       $}$           ${\ displaystyle R = R \ backslash \ {r \}}$     
       For all neighbors  $j\in R$           $j$       $\in$       $R$           ${\ displaystyle j \ in R}$       perform vertices
         If a  $\alpha (j)>\max({\overline {\alpha }}(s),c_{s,j})$           $α$       $($       $j$       $)$       $>$       $max$       $($           $α$       $¯$           $($       $s$       $)$       $,$         $c$         $s$       $,$       $j$           $)$           ${\ displaystyle \ alpha (j)> \ max ({\ overline {\ alpha}} (s), c_ {s, j})}$       then
           Set  $\alpha (j)=\max({\overline {\alpha }}(s),c_{s,j})$           $α$       $($       $j$       $)$       $=$       $max$       $($           $α$       $¯$           $($       $s$       $)$       $,$         $c$         $s$       $,$       $j$           $)$           ${\ displaystyle \ alpha (j) = \ max ({\ overline {\ alpha}} (s), c_ {s, j})}$     
           $\beta (j)=s$           $β$       $($       $j$       $)$       $=$       $s$           ${\ displaystyle \ beta (j) = s}$     
         end if
       end of cycle
     end if
   end if
 end bye

Asymptotic Behavior

Let be

c_{n}^{*}

{\ displaystyle c_ {n} ^ {*}}

denotes the optimal value of the function for n performers and n jobs. If prices

c_{ij}

{\ displaystyle c_ {ij}}

are selected from a uniform distribution on the segment (0,1), then ^[9]

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

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

and

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

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

Links

² ¹ ² Assignment Problems , Rainer Burkard, Mauro Dell'Amico, Silvano Martello, 2009, Chapter 6.2 " Linear Bottleneck Assignment Problem " (p. 172)
↑ DR Fulkerson, I. Glicksberg, and O. Gross. A production line assignment problem. Tech. Rep. RM-1102, The Rand Corporation, Santa Monica, CA, 1953.)
↑ R. Garfinkel. An improved algorithm for bottleneck assignment problem. Oper. Res. 19: 1747-1751,1971.
↑ OH Ibarra and S. Moran. Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication. Inform. Process. Lett., 13: 12–15, 1981.
↑ D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Computing, 9: 251–280, 1990.
↑ H. Alt, N. Blum, K. Mehlhorn, and M. Paul. Computing a cardinality in a bipartite graph in time $O\left(n^{1{,}5}{\sqrt {m/\log n}}\right)$ ${\ displaystyle O \ left (n ^ {1 {,} 5} {\ sqrt {m / \ log n}} \ right)}$ . Inform. Process. Lett., 37: 237–240, 1991.
↑ O. Gross. The bottleneck assignment problem. Tech. Rep. P-1630, The Rand Corporation, Santa Monica, CA, 1959.
↑ U. Derigs and U. Zimmermann. An augmenting path method for solving bottleneck assignment problems. Computing, 19: 285–295, 1978.
↑ Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research , 36 (2): 205-226, 2011.

[assp-1] ² ¹ ² Assignment Problems , Rainer Burkard, Mauro Dell'Amico, Silvano Martello, 2009, Chapter 6.2 " Linear Bottleneck Assignment Problem " (p. 172)

[2] DR Fulkerson, I. Glicksberg, and O. Gross. A production line assignment problem. Tech. Rep. RM-1102, The Rand Corporation, Santa Monica, CA, 1953.)

[3] R. Garfinkel. An improved algorithm for bottleneck assignment problem. Oper. Res. 19: 1747-1751,1971.

[4] OH Ibarra and S. Moran. Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication. Inform. Process. Lett., 13: 12–15, 1981.

[5] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Computing, 9: 251–280, 1990.

[6] H. Alt, N. Blum, K. Mehlhorn, and M. Paul. Computing a cardinality in a bipartite graph in time $O\left(n^{1{,}5}{\sqrt {m/\log n}}\right)$ ${\ displaystyle O \ left (n ^ {1 {,} 5} {\ sqrt {m / \ log n}} \ right)}$ . Inform. Process. Lett., 37: 237–240, 1991.

[7] O. Gross. The bottleneck assignment problem. Tech. Rep. P-1630, The Rand Corporation, Santa Monica, CA, 1959.

[8] U. Derigs and U. Zimmermann. An augmenting path method for solving bottleneck assignment problems. Computing, 19: 285–295, 1978.

[9] Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research , 36 (2): 205-226, 2011.