A Fast Parametric Assignment Algorithm with Applications in Max-Algebra

作者：Gassner Elisabeth; Klinz Bettina^*

来源：Networks, 2010, 55(2): 61-77.

DOI：10.1002/net.20288

• parametric optimization
• assignment problem
• max-algebra
• characteristic max-polynomial
• essential terms

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 circle plus b = max(a, b) and a circle times 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(lambda)(i, j) = c(i, j) - b(i, j)lambda for (i, j) is an element of E. The task is to find an assignment with minimum weight with respect to the parametric weights c(lambda) for all values of lambda. We develop an algorithm which solves the special case for which b(i, j) is an element of {0,1} for all (i, j) e E in O(mn n(2) 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 O(n(3)) time and thus improves upon the best-known algorithm for computing the characteristic max-polynomial due to Burkard and Butkovic (Appl Math 130 (2003), 367-380) by a factor of n.

• 出版日期2010-3