July 1-2, 2024
Speakers
Sophie Huiberts, CNRS: Open problems about the simplex method
The simplex method is a very efficient algorithm, but little is understood about why it is so. In these lectures we will learn about a few of the state-of-the-art theories for explaining this observation and what their shortcomings are. We will discuss what it takes for a mathematical model to explain an algorithm’s qualities. Following this, we question what the simplex method really is, and learn what LP solver developers teach us about where theory can go next.
Along the way we will talk about women’s history, Newton’s laws of motion, and the moral and political implications of the diet problem.
Sophie Huiberts is a CNRS researcher at LIMOS in Clermont-Ferrand, France. She performed her PhD research at Centrum Wiskunde & Informatica (CWI) in Amsterdam and was a Simons fellow at Columbia University in NYC. Her research focuses on the algorithms typically incorporated in popular MIP solvers such as the simplex method, interior point methods, cutting planes and branch-and-bound.
Vera Traub, University of Bonn: Approximation algorithms for Steiner trees
The Steiner tree problem is one of the most studied network design problems. It asks to connect a given set of terminals in the cheapest
possible way.
In these lectures we will give an introduction to approximation algorithms for Steiner trees. In particular, we will discuss a new local search technique inspired by recent progress on related network design problems and discuss possible directions for future research.
Vera Traub is a professor at the University of Bonn, working in the area of combinatorial optimization and approximation algorithms. She obtained her PhD in 2020 from the University of Bonn and afterwards spent two years as a postdoctoral researcher at ETH Zurich. In 2023 she received a Maryam Mirzakhani New Frontiers Prize and a Heinz Maier-Leibnitz Prize for her work on approximation algorithms for the traveling salesman problem and network design problems.
Neil Olver, London School of Economics: Equilibrium behaviour of flow-over-time traffic models
Flows over time, introduced already by Ford and Fulkerson, are by now classical objects in combinatorial optimization. Selfish routing – the study of equilibrium behaviour in network congestion games – has received a lot of attention in the past few decades. The combination of the two – the study of equilibria of truly dynamic, time-varying traffic models – is a more recent topic. In the Vickrey bottleneck model (or deterministic queueing model), congestion is modelled through time-varying queues that form whenever the flow into a link exceeds its capacity. In these lectures, I will give an overview of our theoretical understanding of equilibrium behaviour in this model, which exhibits a rich combinatorial structure. Classical tools, including LP duality, will play a starring role. Many fundamental questions remain open, and I will mention a number of them.
Neil Olver is an Associate Professor in the Department of Mathematics at the London School of Economics and Political Science. He obtained his PhD from McGill University in 2010, after which he spent several years as an Instructor in Applied Mathematics at MIT and as faculty at the Vrije Universiteit Amsterdam before joining LSE.
Neil works broadly in combinatorial optimization. His recent work focuses on approximation algorithms for network design problems; understanding the structure of equilibria in flow-over-time traffic models; and strongly polynomial algorithms for generalized flow problems. He has received a number of grants for his work, including VENI and VIDI grants from the Dutch Science Foundation.
Registration
Please visit the Registration page in order to register.