Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS167, part 1: Computational tropical geometry
Time:
Wednesday, 10/Jul/2019:
3:00pm - 5:00pm

Location: Unitobler, F013
53 seats, 74m^2

Presentations
3:00pm - 5:00pm

Computational tropical geometry

Chair(s): Kalina Mincheva (Yale University), Yue Ren (Max Planck Institute for Mathematics in the Sciences, Germany)

This session will highlight recent advances in tropical geometry, algebra, and combinatorics, focusing on computational aspects and applications. The area enjoys close interactions with max-plus algebra, polyhedral geometry, combinatorics, Groebner theory, and numerical algebraic geometry.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

The tropical geometry of shortest paths

Michael Joswig1, Benjamin Schroeter2
1Technische Universität Berlin, 2Binghamton University

We study parameterized versions of classical algorithms for computing shortest paths. This is most easily expressed in terms of tropical geometry. Applications include the enumeration of polytropes, i.e., ordinary convex polytopes which are also tropically convex, as well as shortest paths in traffic networks with variable link travel times.

 

Tropicalization of semialgebraic sets arising in convex optimization

Xavier Allamigeon1, Stephane Gaubert1, Mateusz Skomra2
1INRIA & CMAP, 2École normale supérieure de Lyon

Linear programming (LP) is the simplest and most studied class of conic optimization problems. It consists in minimizing a linear function over a convex cone that is polyhedral. Important generalizations of LP include semidefine and hyperbolic programming, in which we allow the underlying cone to have a more complicated structure. In the case of semidefinite programming, the cone is defined by linear matrix inequalities, while a hyperbolicity cone is defined by imposing a positivity condition on the eigenvalues of a hyperbolic polynomial. In all three cases, the underlying cones are semialgebraic, which implies that we can study them over arbitrary real closed fields, such as the nonarchimedean field of real Puiseux series. The tropicalization of such cone is then defined as its image under the nonarchimedean valuation.

In this talk, we discuss the structure of these tropicalizations and the related computational problems. In particular, we study how the structure of tropical spectrahedral cones is more restrictive in comparison to the structure of arbitrary tropical convex cones. To obtain these results, we study the structure of arbitrary tropical semialgebraic sets. We also show how tropical convex cones encode stochastic mean payoff games and how this can be used, in the case of generic tropical spectrahedra, to solve the associated feasibility problems.

 

Linear algebra and convexity over symmetrized semirings, hyperfields and systems

Marianne Akian1, Stephane Gaubert1, Louis Rowen2
1INRIA & CMAP, 2Bar-Ilan University

Rowen introduced a notion of algebraic structure, called systems, which unifies symmetrized tropical semirings, supertropical semirings, and hyperfields. We study linear algebra and convexity over systems. We identify cases in which the row rank, column rank, and submatrix rank of a matrix are equal. We also discuss Helly and Carathéodory numbers.

 

Dynamics of priority: from emergency call centers to tropical polynomial systems

Marianne Akian, Xavier Allamigeon, Stephane Gaubert, Marin Boyet
INRIA & CMAP

Priority mechanisms are a key element of the management of emergency call centers. These mechanisms can be modeled by dynamical systems with a piecewise affine transition mapping, determined by a rational map in the tropical semifield. Performance indicators can be inferred from stationary regimes. The latter are determined by solving structured tropical polynomial systems: these are analogous to the non-linear eigenproblems associated to Markov decision processes, but priority rules lead to negative "probabilities".

We exploit this analogy to obtain algorithms for classes of tropical polynomial systems. In particular we relate Jensen's tropical homotopy algorithm to the shadow vertex algorithm applied to the linear programming formulation of Markov decision processes. We exhibit a class of tropical polynomial systems that can be solved in polynomial time, as well as a corresponding class of ordinary polynomial systems for which a positive solution can be approximated in polynomial time. We finally discuss open problems concerning priority dynamics. This work originates from an ongoing case study of the 17-18-112 emergency call center in the Paris area.