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