Answers are grounded in this paper and cite their sources.
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 2 n 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 𝒪( m n + 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 𝒪( n 3 ) 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 .
No takes yet. Share an insight, caveat, or question.
Gassner et al. (2009) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: