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.