A fast parametric assignment algorithm with applications in max‐algebra
Elisabeth Gassner, Bettina Klinz · Networks · 2009
Abstract This article presents a fast algorithm for a class of parametric assignment problems. Moreover, it is shown how this algorithm can be applied to a problem arising in the so‐called max‐algebra which results as an analogue of classical linear algebra by replacing the classical addition and multiplication by a ⊕ b = max(a,b) and a ⊗ b = a + b, respectively. An instance of the linear parametric assignment problem is given by a bipartite graph G = (U,V,E) with 2n vertices, m edges and affine‐linear parametric edge weights cλ(i,j) = c(i,j) − b(i,j)λ for (i,j) ∈ E. The task is to find an assignment with minimum weight with respect to the parametric weights cλ for all values of λ. We develop an algorithm which solves the special case for which b(i,j) ∈ {0, 1} for all (i,j) ∈ E in 𝒪(mn+n2 log n) time. Our algorithm can be extended to solve the special parametric assignment problem which arises in connection with computing the essential terms of the so‐called characteristic max‐polynomial. The resulting algorithm runs in 𝒪(n3) time and thus improves upon the best‐known algorithm for computing the characteristic max‐polynomial due to Burkard and Butkovič (Appl Math 130 (2003), 367–380) by a factor of n. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010