Research

I work broadly in combinatorial optimization and adjacent areas, particularly probability and game theory. A lot of my work (though by no means all) concerns optimization problems with a network structure, and I am currently funded by a VIDI grant of the Dutch Science Foundation entitled “Usable Algorithms for Network Design” on this topic. Below, some of my current research interests are listed.

Network design

Network design problems are typically motivated by applications in communication, transport and logistics networks. See here for some relevant publications; some of my favourite topics are:

Thin trees. The thin tree conjecture asks whether, in a sufficiently well-connected graph, one can find a spanning tree that crosses every cut using only a small fraction of the available edges. This is a beautiful and fundamental open question with connections to the travelling salesman problem. In recent work with Nathan Klein, we proved an easier version of the conjecture where we only bound the thinness on a specified laminar family of cuts.

Graph partitioning. We recently (STOC 2026) gave improved algorithms for the nonuniform graph partitioning problem: given a graph, what is the “best” way to divide the graph into parts of specified sizes, so that not too many edges of the graph cross between different parts?

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: for instance, the approximability of robust network design in the single-commodity setting is completely open, and interesting for rather diverse reasons.

Strongly polynomial algorithms for generalized flow

One of the biggest open problem in optimization asks: is there a strongly polynomial algorithm for linear programming? “Strongly polynomial” refers to a certain refined notion of efficiency; essentially, that the algorithm is efficient when working in a real model of computation where basic arithmetic operations on real numbers are considered to have unit cost.

In joint work with Daniel Dadush, Zhuan Khye Koh, Bento Natura and László Végh, we gave the first strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column of the constraint matrix. This is equivalent to the minimum cost generalized flow problem, a network flow problem where flow is scaled as it traverses an edge.

Theoretical aspects of traffic networks

I am interested in fundamental questions about equilibrium behaviour—how traffic should be expected to behave—in simplified, abstracted models of traffic, taking the perspective of computation, optimization, and algorithmic game theory. I have been particularly fascinated by a very natural, seemingly simple, but in fact exceedingly rich model where traffic congestion is modelled through simple point queues, induced when traffic flow entering a link exceeds the capacity of the link. It is perhaps the simplest model that captures the dynamic, time-varying behaviour of traffic in a satisfactory way, and is well-studied by transportation economists as the “Vickrey bottleneck model”.

There are many fascinating questions about the structure of equilibria in this model; basic questions about even computing equilibria are open. But we have been able to make some progress in our understanding of the structure of equilibria. We showed that under the appropriate necessary conditions (the capacity of the network should be no less than the flow rate into the network), equilibrium behaviour eventually “settles down” into a situation where queue lengths no longer vary, and hence remain bounded. More recently, we have answered some key questions that show that equilibria are “stable” in various important senses. For instance, the behaviour of approximate equilibria, and of equilibria in a natural atomic version of the model, does not stray too far from the behaviour of exact equilibria in the original model.

Probability

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.

As one example, appointment scheduling is a topic motivated (especially) by applications in healthcare. The goal is typically to schedule appointments so as to balance patient waiting times and doctor/surgery idle times, when faced with patient service times that are highly stochastic. We obtain the first theoretical guarantees for certain popular heuristics (principally, “smallest-variance-first”, which takes the natural approach of putting the patients with the most predictable service times first), and seem to have been the first to view the problem through the lens of approximation algorithms.