Aarhus University Seal / Aarhus Universitets segl

Linear and rational factorization of tropical polynomials

Bo Lin (University of Texas)
Algebra and Computer Science Seminar
Friday, 6 April, 2018, at 12:30-13:30, in Aud. G1 (1532-116)
In the tropical arithmetic, there is no division and factorization is already an NP-Complete problem for bivariate tropical polynomials. We present an algorithm for linear and rational factorization of a rich class of tropical polynomials in $n$ variables, some of which have appeared in economics, discrete convex analysis, and combinatorics. Our approach relies on the decomposition of lattice polytopes into signed Minkowski sums and we convert this decomposition to a linear algebra problem.
Contact person: Anders Nedergaard Jensen