1.5 You name it—we have it 13 This crucial observation is emphasized by renaming the two basic operations into new “multiplication” and “addition”: a b = a + b, a b = max(a, b). The previous identity takes the more familiar shape of the dis- tributive law: a (b c) = a b a c. Of course, operations and are commutative and associative. After recycling the traditional shorthand x n = x · · · x (n times), we can introduce polynomials as well as matrix multiplication, determinants, etc. For example, the tropical determinant of the matrix A = (aij) is defined by evaluating the expansion formula (see page 9) tropically and ignoring the signs of permutations σ involved in the classical formula for determinant [396, 408]:8 dettrA = σ∈Sym n (a1,σ(1) · · · an,σ(n)) = max σ∈Sym n (a1,σ(1) + · · · + an,σ(n)). Here the “sum” is taken over the set Sym n of all permutations of indices 1, . . . , n for example, dettr a b c d = max(a + d, b + c). Therefore the “sum” involves n! “monomials”—exactly as in the case of ordinary determinants. Let us return for a second to our discussion of the complexity of the evaluation of determinants in two models of computation: choice-based and choiceless. It is not obvious at all that a tropical determinant can be evaluated us- ing O(n3) elementary operations—but it is true. The evaluation of the tropical determinant is the classical assignment problem in discrete optimization and the bounds for its complexity are well known [400, Corollary 17.4b]. Indeed, finding the value of the trop- ical determinant amounts to finding a permutation i σ(i) which maximizes the sum a1,σ(1) + · · · + an,σ(n). This is an old problem of applied discrete optimization: a company has bought n machines M1,. . . , Mn which have to be assigned to n factories F1,.. . , Fn the expected profit from assigning machine Mi to factory Fj is aij find the assignment Mi Fσ(i) which maximizes the expected profit a1,σ(1) + · · · + an,σ(n).
Previous Page Next Page