## 8 A Faster Parametric Assignment Algorithm
### A Brief Review of the Gassner-Klinz Algorithm and Its Adaptation
Note that it is at this point that we make changes that need to be made because the coefficients \(k_{ij}\) in our objective function have the opposite sign compared with the corresponding \(b_{ij}\) in the GKA. The remaining arcs, called _forward arcs_, as well as their costs, remain the same as in graph \(G\). Graph \(N(A)\) has no cycles with a negative cost for \(\lambda=\lambda^{\prime}\). Let us increase parameter \(\lambda\) and let \(\lambda_{c}\) be the minimum value of \(\lambda\) such that in the residual graph \(N(A)\), there is a cycle \(C\) with zero cost, \(w(C,\lambda_{c})=0\), and \(w(C,\lambda)<0\) when \(\lambda>\lambda_{c}\). Value \(\lambda_{c}\) and cycle \(C\) are the _critical point_ and _critical cycle_, respectively. The assignment \(A\) remains a minimum-cost assignment in the interval \(\lambda\in[\lambda^{\prime},\lambda_{c}]\). Then, in the interval \(\lambda\in[\lambda_{c},\lambda^{\prime}{}_{c}]\), where \(\lambda^{\prime}{}_{c}\) is a critical point next to the critical point \(\lambda_{c}\), the minimum-cost assignment changes to \(A^{\prime}=(A\backslash C^{\prime})\cup(C^{\prime}\backslash A)\), where \(C^{\prime}\) is a subset of the arcs obtained from the \(C\) by replacing all the backward arcs with the corresponding forward arcs; the cost of \(A^{\prime}\) changes to \(w(A^{\prime},\lambda)=w(A,\lambda)+w(C,\lambda)\). It is worth noticing at this stage that the following essential property is valid: when the parameter \(\lambda\) increases, the objective function of our problemalso increases, while the objective function in the Gassner-Klinz problem decreases (see Figure 4). At point \(\lambda=\lambda_{c}\), the costs of assignments \(A\) and \(A^{\prime}\) are equal; \(w(A,\lambda_{c})=w(A^{\prime},\lambda_{c})\). By changing the cost and the direction of all the arcs in cycle \(C\) to opposite ones in the residual graph \(N(A)\), one obtains the residual graph \(N(A^{\prime})\). The following question is crucial: Starting with the minimum-weight assignment \(A\) for \(\lambda=\lambda^{\prime}\), how can one determine the critical point \(\lambda_{c}\)? Recall that in the residual graph \(N(A)\), for \(\lambda=\lambda^{\prime}\), there are no cycles with a negative cost, and that when the parameter \(\lambda\) increases, some cycle \(C\) with a zero cost appears only at the point \(\lambda=\lambda_{c}\), \(w(C,\lambda_{c})=0\). To determine this cycle, we follow the approach proposed in [31] and also use the parametric shortest path algorithm of [PERSON] [32] and its improved version in [33]. Let us take some vertex \(s\) as the source vertex in the graph \(N(A)\) and build a shortest path tree \(T(\lambda)=T(\lambda^{\prime})\) for \(\lambda=\lambda^{\prime}\). As \(\lambda\) increases from \(\lambda^{\prime}\) to \(\lambda_{c}\), the tree \(T(\lambda)\) is transformed; namely, some arcs are replaced by others. The values of \(\lambda\) at which the tree changes are called breakpoints. Let us denote these breakpoints in ascending order as \(\mu_{1}\), \(\mu_{2}\), and \(\mu_{l}\). Denote \(T_{r}=T(\lambda)\), \(\lambda\in[\mu_{r},\,\mu_{r+1}]\), where \(r=0\), \(1\), \(2\), \(\ldots,1-1\). Tree \(T_{1-1}=T(\lambda)\), where \(\lambda\in[\mu_{l-1},\,\mu_{l}]\), is the last constructed tree. Since in our problem of fleet assignment \(\mu_{l}\
eq\infty\), it follows that a zero-weight cycle \(C\) appears in \(N(M)\) at \(\lambda=\mu_{l}\), and at \(\lambda>\mu_{l}\), the weight of the cycle \(C\) becomes negative. This means that \(\mu_{l}\) is a critical point, and \(\lambda_{c}=\mu_{l}\). At each breakpoint, the slope of any path can only decrease. Since at each breakpoint, at least one path to a vertex changes, the number of breakpoints is limited to \(O(n^{2})\). Thus, it turns out that transforming the current assignment into a new one at a critical point is simpler than solving the assignment problem anew. The steps of the modified GKA adapted for solving our **PAP** problem are the following Algorithm 2:  
**Step 1. Initialization**  
1.1.