Polyhedral Split Decomposition of Tropical Polytopes for Directed Distances
Shungo Koichi · 2010
Abstract In the last decade, tropical geometry has been attracted a lot of attention in various fields such as the algebraic geometry, computational biology, and physics. The tropical polytope in the tropical geometry was introduced by Develin and Sturmfels as a counterpart of the polytope in the (ordinal) geometry. Recently, in the theory of directed multiflows, it has been shown by Hirai and the author that the dual problem of the µ-weighted maximum multiflow problem on Eulerian networks reduces to a facility location problem on the tropical polytope for µ, where the weight µ is regarded as a directed distance. Moreover, if the dimension of the tropical polytope for µ is at most one, the µ-weighted maximum multiflow problem has an integral optimal multiflow for any Eulerian networks. In this paper, we apply the polyhedral split decomposition to the tropical polytope for a directed distance d. As a result, a tropical polytope of dimension one turns out to be a Minkowski sum of a zonotope, a linear space, and a nonnegative orthant.