Linear and Rational Factorization of Tropical Polynomials

Abstract

Already for bivariate tropical polynomials, factorization is an NP-Complete problem. In this paper, we give an efficient algorithm for factorization and rational factorization of a rich class of tropical polynomials in $n$ variables. Special families of these polynomials have appeared in economics, discrete convex analysis, and combinatorics. Our theorems rely on an intrinsic characterization of regular mixed subdivisions of integral polytopes, and lead to many open problems of interest in discrete geometry.

arXiv comment27 pages, 4 figures

References in corpus (9)

• Tropicalizing the simplex algorithm
• Weighted digraphs and tropical cones
• Tropical Geometry of Deep Neural Networks
• Factorization of polynomials in one variable over the tropical semiring
• Tropical Geometry and Mechanism Design
• Product-Mix Auctions and Tropical Geometry
• An Elementary Proof of the Fundamental Theorem of Tropical Algebra
• Efficient edge-skeleton computation for polytopes defined by oracles
• Generalized Permutohedra from Probabilistic Graphical Models

Cited by in corpus (2)

• Bounding The Number of Linear Regions in Local Area for Neural Networks with ReLU Activations
• The Tropical Division Problem and the Minkowski Factorization of Generalized Permutahedra