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)


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.


Click here for the abstracts.

Click here for the schedule.

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