I work broadly in the area of combinatorial optimization, as well as its interactions with probability and game theory. Below you can find a brief overview of my main research directions. (Click on a section to expand it.)

  • Network design

    Network design

    Algorithmic problems motivated by the design of efficient communication and transportation networks

    Network design problems are typically motivated by applications in communication, transport and logistics networks.

    Steiner tree: one of the most fundamental network design problems, the Steiner tree problem asks for the cheapest way to connect a subset of the nodes of a given network. Despite being very simple to state, it is an NP-hard problem, and there is much left to be understood. I am currently very interested in the so-called “bidirected cut relaxation”.

    Robust network design: this refers to a class of problems where we wish to design networks in the face of uncertain or varying usage. Robust network design provides a flexible way to model this uncertainty, and a host of fascinating algorithmic problems arise from it. Along with Navin Goyal and Bruce Shepherd, we resolved the “VPN Conjecture”, a long-standing open question in the area. Challenging and interesting questions remain.

    Relevant publications.

  • Algorithmic game theory

    Algorithmic game theory

    Understanding the impact of strategic behaviour

    I am very interested in the interaction between combinatorial optimization and game theory.

    Dynamic models of traffic: There is a large literature on how strategic route choices made by users can impact road networks. But dynamic models of traffic, where time plays an explicit role in the model, are very poorly understood from this perspective.

    Coordination mechanisms: In many games (e.g., routing and scheduling games), there is the possibility to modify the incentives of the game, for example by introducing delays or tolls, or by giving preference to some users over others.

    Relevant publications.

  • Probability

    Probability

    A crucial tool for modelling and algorithm design

    Many, many problems are of a stochastic nature. Moreover, probabilistic methods are a crucial tool in the modern design of approximation algorithms. I am interested in these interactions of probability with operations research and algorithms, but also for its own sake.

    Relevant publications.