## 8 A Faster Parametric Assignment Algorithm
### A Brief Review of the Gassner-Klinz Algorithm and Its Adaptation  
The GKA algorithm aims to solve the parametric assignment problem described in Table 4 for _all possible_ values of parameter \(\lambda\); its worst-case complexity is \(O(n^{3})\). That is, the same as that for the standard (non-parametric) linear assignment problem. In contrast to the Newton-type Algorithm 1, the GKA does not solve each of the \(O(n)\) assignment problems appearing at critical points but rather solves an assignment problem only once and then transforms the obtained assignment into a new one with certain local operations so that the minimum-cost assignments for all the values of \(\lambda\) are found in \(O(nm+n^{2}\) log \(n)\) time, where \(m\) and \(n\) are the number of arcs and the number of nodes, respectively, in an underlying bipartite graph described below. We will follow the same idea of the GKA and adapt it, adding necessary changes, in order to take into account that the objective functions in the two problems are different (see Table 4). Since the two optimization problems in Table 4 are very close, it suffices to replace \(c_{\lambda}(i,j)=(c_{ij}-\lambda\cdot b_{ij})\) in the Gassner-Klinz problem by \(c^{\prime}{}_{\lambda}(i,j)=(c^{\prime}{}_{ij}-\lambda\cdot b^{\prime}{}_{ij })=(-e_{ij}-\lambda\cdot(-k_{ij}))\) and then use the existing algorithm GKA. In this case, the slope of the parametric objective function in the derived problem (which, obviously, in this case, will be our PAP) will be positive and will decrease with the growth of parameter \(\lambda\) until \(L(\lambda)\) becomes zero, whereas the slope of the objective function in the original Gassner-Klinz problem is negative and its absolute value increases when the parameter increases to infinity (see Figure 4). Another observation is that in the original Gassner-Klinz problem, \(b_{ij}\in[0,1]\), whereas \(b^{\prime}{}_{ij}\) are to be \(\{0,-1,-2,-3\}\); however, this difference can be easily overcome, and it does not influence the algorithm complexity. Finally, the starting point and the stopping rule are different in the GKA and in the modified algorithm. Indeed, when solving the PAP problem, one does not need to solve the assignment problems at all the critical points for all possible \(\lambda\in(-\infty,\)\(+\infty)\); rather, the modified algorithm starts with a known lower bound of the parameter and stops as soon as the cost \(L(\lambda)\) of a current assignment becomes zero. Below, for the reader's convenience, we review the proposed modification of the GKA and, in order to give a more complete picture, describe the steps of the adapted algorithm. For easier comparison, in this subsection, we borrow graph-theoretic terminology from [31] to describe the modified algorithm. Consider the parametric assignment problem as a minimum-cost matching problem in a bipartite graph \(G=(U,V,W)\), where the vertices \(U\) and \(V\) correspond, respectively, to the rows and columns of the matrix \(\mathbf{W}(\lambda)\), \(\left\downarrow U\right\downarrow=\left\downarrow V\right\downarrow=n\), \(\left\downarrow W\right\downarrow=m\). Arc \((i,j)\in W\) only if arc \((i,j)\) exists in the graph \(G_{gen}\). Arcs lead from set \(U\) to set \(V\). The parametric cost of arcs \((i,j)\in W\) is \(w(i,j)=(\lambda\cdot k_{ij}-e_{ij})\), where \(i\in U\) and \(j\in V\), i.e., the element of the matrix \(w_{ij}\in W(\lambda)\) is equal to the cost of the arc \((i,j)\), \(w(i,j)=w_{ij}\). Let \(A^{*}(\lambda^{\prime})\) be a minimum-cost assignment in graph \(G\) for \(\lambda=\lambda^{\prime}\). Exactly as in [31], we associate with the graph \(G\) and assignment \(A=A^{*}(\lambda^{\prime})\) a residual graph \(N(A)=(U,V,W^{*})\) constructed as follows: All the arcs \((i,j)\in A\), where \(i\in U\) and \(j\in V\), are replaced by _backward arcs_\((j,i)\) of cost \(w(j,i)=-w(i,j)=(-\lambda\cdot k_{ij}+e_{ij})\).