Calculating essential terms of a characteristic maxpolynomial

Let us denote a ⊕ b = max(a, b) and a ⊗ b = a + b for a, b ∈ R ∪ {−∞} and extend this pair of operations to matrices and vectors in the same way as in conventional linear algebra. We present a polynomial algorithm for finding all essential terms of the characteristic maxpolynomial χA(x) = per(A ⊕ x ⊗ I) of matrices A with entries from Q ∪ {−∞}. In the cases when all terms are essential this algorithm also solves the following problem: Given an n × n matrix A and k ∈ {1, …, n}, find the maximal optimal value for the assignment problem over all k × k principal submatrices of A.