Permanents, max algebra and optimal assignment (Q1899397)

The max algebra consists of the set \({\mathcal M}= \mathbb{R} \cup \{-\infty\}\) equipped with two binary operations, \(a \oplus b = \max (a,b)\) (addition in \(\mathcal M\)) and \(a \otimes b = a + b\) (multiplication in \(\mathcal M\)). For a square matrix, its permanent over \(({\mathcal M}, \oplus, \otimes)\) is simply the maximum diagonal sum of the matrix. Several results are proved for the permanent over the max algebra \(\mathcal M\), which are analogues of classical results for the permanent of a nonnegative matrix.