Research Topics

Below you find a description of my research areas, each appearing with the related publications. Papers that cross different subjects appear multiple times.

Matching problems

In matching problems we want to pair agents as to respect certain feasibility condition and / or maximize objective functons. They are used to model problems arising in job placement, school choice, machine learning, and more. As such, they lie at the intersection of operations research, computer science, and economics, and have historically played a fundamental role in each of those areas. My research in this area has mainly followed three strands.
 
Algorithms and Structure for Matching Markets. In matching markets arising, e.g., in school choice, resource allocations, etc., agents have preferences of their possible partners. For such markets, I have investigated algorithmic questions: Can we efficiently obtain matchings of probably good quality, in a well-defined sense? Many algorithms in turn rely on structural results: which are the underlying mathematical structures of (subsets of) matchings, and how can they be exploited algorithmically? Much of my work here deals with extensions of the classical concept of stability, introduced by Gale and Shapley in 1962. I have studied popular matchings (MP5, MP6, MP8), legal / von Neumann-Morgenstern assignments (MP7, MP14), matchings with blocking costs (MP9), problems where preferences of agents are described by choice functions (MP11), and stable matchings in two-stage settings or when multiple siblings apply simultaneously (MP16, MP20). Some of those algorithms rely on and / or extend more general mathematical techniques, such as posets associated to sets of matchings and Birkhoff's representation theorem for distributive lattices (MP11, MP16, MP20), or pivoting procedures like Scarf's algorithm (MP15, MP19). I have moreover investigated stable matchings in more general settings like non-distributive lattices (MP18) and hypergraphs (MP19).
 
Analysis of Matching Markets. To tune matching algorithms to real-world settings, it is important to understand the effect of the current rules/mechanisms and of their alternatives on the quality of the solutions for the agents of the market. To answer this question, I have investigated mechanisms to assign reserved seats (MP12) and scholarships (MP10), as well as the impact of the length of preference lists (MP21) on the quality of the output matchings.
 
If you are interested in learning more about matching markets, the videos below from the bootcamp I gave at ICERM, Brown University, on Matching theory and school choice discuss several problems, results, and applications in the area.
 

 
Weighted matching problems. In weighted matching problems, we are given a graph with weights on the edges. The input can be interpreted in multiple ways. For instance, in (extensions of) the classical assignment game, the nodes are buyers and sellers, and the goal is to find a matching that gives an equilibrium in the market. In MP17, we give an algorithm for computing such a matching in very general markets -- technically, where buyers' utility satisfy gross substitutes and utility is imperfectly transferable. Another example is given by the problem of matching drivers to riders in modern ride-sharing platforms: this is often modelled as an online matching problem, where one side of the market is known in advance (typically, the drivers), while the other comes in an online fashion. The weight of an edge denotes the time that it takes to a driver to serve a rider, and the goal is to find a matching of minimum weight. In practice, simple algorithms are often used to solve such matching problems. In MP13, we studied in which settings we can expect the simplest algorithm of all, i.e., greedy, to perform well, as a function of the distributions of the locations of servers and drivers.
A third classical class of problems is given by Edmonds' maximum weighted matching problem, one of the pillars of discrete optimization. This problem can be equivalently be formulated as a maximum (weighted) independent set problem in an auxiliary graph (''line graph''). Researchers have investigated superclasses of line graphs where the (weighted) stable set problem can be solved efficiently. My work here has focused on the class of claw-free graphs. Stable sets in claw-free graphs have been studied since the 70s. Those graphs have applications in problems arising in wireless networks, scheduling, and machine learning. For the maximum weighted stable set problem in claw-free graphs, we gave (the) fast(est) combinatorial algorithms (MP2, MP3), as well the first non-trivial geometric algorithm (MP4). See also MP1.
 
Acknowledgments: My current work on matching problems is supported by an NSF CAREER award and by a Meta Research award.

Exact and approximate formulations for integer programming problems

Integer Programming (IP) aims at maximizing a linear function over the set of integer points that satisfy a finite set of linear constraints. It is used to model problems arising in production planning, logistics, and many more settings. In general, IPs are very hard to solve, hence the study of fast general or problem-specific algorithms for their solutions is a crucial area of research. Geometric algorithms for solving integer optimization problems are highly dependendent on the size of the system of constraints describing the feasible region: the larger its size, the larger the running time of the algorithms (in both theory and practice, assuming all other parameters stay the same). An important problem is therefore to find formulations that exactly or approximately describe the original IP, using a small number of constraints. My research in the area has focused on two strands.
 
Extended formulations. It is often the case that a feasible region can be expressed more succintly as the image under an affine map of a convex set living in an higher dimensional space. Such a convex set is called an extension and its description via a system of constraints an extended formulation for the original feasible region. A typical question I investigate in this area is: what is the minimum number of constraints in a (linear) extended formulation for the feasible region P of a linear program? This is called the extension complexity of P. Papers EF4, EF6, EF9, EF10, EF11, EF12 and the survey EF1 deal with this question for feasible regions of problems arising in combinatorial optimization, including matching problems under preferences (aka matching markets). Papers EF2, EF8 deal with more general integer and quadratic problems.
 
Somehow suprisingly, questions on extension complexity can be reformulated, and sometimes solved, using techniques from seemingly far away areas of mathematics and computer science, like algebraic geometry and boolean Fourier analyis. I am / have been investigating some of these connections. In EF3, EF7 we explore in particular the relationship between extension complexity and communication protocols, a classical topic in theoretical computer science. In EF5 we bound the minimum increase in the number of variables needed to obtain certain extended formulations with ''few'' constraints. Current ongoing work also deals with the relationship between extended formulations and Sum of Squares proofs.
 
Acknowledgments: My current work in this area is supported by an award from the AFOSR. Previously, it was supported by an award from the ONR, and an award and then a gift from the Swiss National Science Foundation.

Cutting planes. In order to obtain an approximation to the value of the optimal solution to an IP, a classical approach relaxes the integrality constraints, and solves the (much easier) resulting linear program. However, the solution produced by this technique may be very far away from the optimum integer solution. We want therefore to improve the formulation of the problem by adding additional inequalities called cutting planes (or cuts).
 
Which cutting planes allow us to obtain a (much) better approximation to the optimal integer solution? Which moreover lead to a formulation that can be easily solved? In CP1, CP2, CP4, we investigate properties of cutting planes that are valid for any IP, that go under the name of Chvatal-Gomory and Split cuts. In CP3, CP6, CP7 we investigate families of cutting planes that are valid for knapsack problems. In CP5 we investigate how Machine Learning techniques can be used to guide the selection of the best cutting planes.

Knapsack and other problems in combinatorial optimization

Many problems in Discrete Optimization can be formulated in a combinatorial way as the problem of choosing a set of maximum profit from a finite family of feasible sets. In this area, I have investigated fast algorithms, hardness, and hardness of approximation for graph optmization problems such as maximum stable (independent) set (KP3), coloring (KP2), Traveling Salesman Problem (KP9), total matching (KP10), and for invariant-preserving reductions (KP1). Those problems model applications arising, eg, in allocation of scarce resources such as bandwith, classes,....
 
I have moreover been very interested in knapsack problems. In the classical knapsack problem we want to select a set of objects as to maximize a linear objective function, subject to the constraint that the total weight of the selected objects does not exceed a given capacity. (Extensions of) Knapsack are widely used to model research allocation and financial planning problems. Combinatorial algorithms for knapsack are very well-studied. However, less is known on geometric approaches, both for knapsack and for its minimization counterpart, called minimum knapsack. Some questions on geometric approaches to these problems are studied in KP4, KP6, KP7.
 
In order to model real-world scenarios, several extensions of knapsack have been introduced. One such generalization assumes that the capacity of the knapsack increases over time (as to model a growth in the budget for investments, of the avaialable resources,...). This class of extensions goes under the name of incremental knapsack problems. In KP5, KP8 we study algorithms for certain incremental knapsack problems, and their connections with problems in scheduling. For more problems in combinatorial optimization such as matching and stable set problems that generalize matching, see this section.

Distributional and data-dependent analysis of algorithms

Classical theory evaluates algorithms in the worst-case scenario. For instance, the quality of an algorithm for the Traveling Salesman problem is determined by the instance where it performs the worst. However, real-world data is rarely adversarial, or even fully random. It is therefore important to analyze and compare algorithms under more restrictive assumptions on the input data, in order to develop a theory of algorithms that better matches the practice, and at the same time to inform practitioners about which algorithm they should use, depending on the assumptions they can make on the data.
 
In DD1, DD2 we study the effectiveness of simple local search and greedy algorithms for the Traveling Salesman problem and the minimum weight perfect matching problem respectively, showing that under fairly general assumptions on the data these simple algorithms perform almost optimally. We also discuss the robustness of those assumptions, showing that when they are relaxed a bit the performance of the algorithms quickly degrades.
 
In DD3, we investigate two popular algorithms for assigning seats to disadvantaged students in school choice markets, and give a sufficient condition, that we term high competitiveness, under which one algorithm can be proved to outperform the other (from the point of view of disadvantaged students). We also give evidence showing that this assumption is verified in relevant markets.
 
In DD4, we investigate the effect of allowing students to submit longer preference lists on the quality of the output matching, assuming that students are ranked following a serial dictatorship order, and their (partial) preference lists are sampled uniformly at random. We show a sharp distinction between students who prefer (in expectation) matchings obtained when lists are longer, and students who instead prefer matchings obtained when lists are shorter.

Discrete Optimization ↔ Machine Learning

Typically, researchers in machine learning have looked at continuous optimization for techniques to solve their problems. However, in the last years, there has been a surge of research at the intersection of machine learning and discrete optimization. On one hand, can discrete optimization techniques solve problems arising in machine learning? On the other hand, can machine learning be used to solve complex discrete optimization problem faster?
 
My research here has focused on showing how certain impossibility results in machine learning can be transferred to results of a similar flavour in optimization (ML2), how machine learning can be embedded in integer programming solvers, as to increase their performance (ML1), and how a classical discrete optimization framework -- submodular function maximization -- can be used together with classical convex optimization algorithms to select the most relevant features of a dataset while training the ML model (ML3).

Miscellanea on polytopes

I have further worked on other geometric problems, mostly on polytopes. These include: an investigation of an intriguing yet very common class of polytopes called 2-level, with connections to statistic and the celerated log-rank conjecture in theoretical computer science, see MI2, MI3; algorithms for finding certain substructures in polytopes, with connections to submodular functions and largest subdeterminants of matrices, see MI1, MI4; pivoting algorithms, see MI5, MI6.