# Workshop: Tropical geometry and the geometry of linear programming

**Dates: **September 20 - 24, 2021**Venue:** online

Organizers: Xavier Allamigeon (Paris), Jesús De Loera (UC Davis), Laura Sanità (Eindhoven), László Végh (London)

**Description:**

Linear optimization is a fundamental tool in modern optimization, for example, it is a key subroutine for the solution/approximation methods of more difficult problems in integer, combinatorial, and non-linear optimization. Thus, the pursuit of more efficient algorithms for solving linear programs has been a driving force in the development of optimization theory, establishing beautiful connections to discrete mathematics, geometry, and analysis. Recent breakthrough results also indicate a deep connection between strongly polynomial solvability of linear programs and geometry, in particular the beautiful area of tropical geometry. Tropical geometry is intimately connected to a variety of important optimization topics, also including mean payoff games and parity games, discrete convex analysis, and market equilibrium computation. The goal of this workshop is to bring together researchers in optimization, tropical geometry, and other related areas, to further deepen the links between these areas, and get a better understanding of the geometry of polyhedra and the behaviour of various linear optimization algorithms.

**If you are interested in attending the workshop, you will find here a link to the online registration**.

You can find the abstracts here.

You can find the schedule here.

## Video recording and slides

**Daniel Dadush: Probabilistic analysis of the simplex method and polytope diameter **

**Alexander Black: Modification of the shadow vertex pivot rule **

**Sean Kafer: Performance of steepest descen in 0/1 LPs **

**Raman Sanyal: Polyhedral geometry of pivot rules **

**Stephane Gaubert: Tropical convexity and its relation with mean payoff games and linear programming**

**Ben Smith: Face structures of tropical polyhedra**

**Georg Loho: Oriented matroids and signed tropical convexity**

**Mateusz Skomra: Separation theorems in signed tropical convexities**

**Marianne Akian: Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria**

**Nathanaell Fijalkow: Understanding and extending the quasipolynomial time algorithms for parity games**

**Cedric Koh: Beyond value iteration for parity games: strategy iteration with universal trees **

**Stephan Weltge: Binary scalar products**

**Steffen Borgwardt: The role of partition polytopes in data analysis**

**Alberto Del Pia: Proximity in concave integer quadratic programming**

**Bento Natura: On circuit imbalance measures and their role in circuit augmentation algorithms**

**Shmuel Onn: Sparse integer programming is FPT**

**Cynthia Vinzant: Log concave polynomials and matroids**

**Noriyoshi Sukegawa: On the diameter of polyhedra and related topics**

**Lionel Pourin: Algorithmic, combinatorial, and geometric aspects of linear optimization**

**Francisco Criado: The dual 1-fair packing problem and applications to linear programming**

**Michael Joswig: Generalized permutahedra and optimal auctions**