We will work on exciting questions at the forefront of current research. The research project will be fixed together with the PREP applicant in one of the following areas of research (or related fields), depending on the applicant’s interest and prior knowledge.
Discrete optimization encompasses mathematical optimization problems that can be represented by a finite (though usually very large) number of possible choices, where the merit of each choice can be quantified by some objective measure. Combinatorial optimization problems are at the heart of numerous decision-making situations. Developing sophisticated mathematical models and algorithms to find optimal or provably near-optimal strategies (approximation algorithms) is an important area of research. Roughly speaking, there are three approaches to discrete optimization: looking at and solving specific problems, often motivated by important real-world applications; developing, studying, and advancing concepts and methodologies (e.g., network models and graph theory) that can be applied to a multitude of problems; and developing key insights such as identifying properties that connect different problems with one another, or analyzing the limits of certain arguments and techniques, often within some kind of abstract framework.
Integer programming is a mighty all-purpose tool that provides a common modeling language and solution method for a myriad of important real-world applications. Because integer-programming problems are, in general, NP-hard, an important direction of research has been the derivation of strong upper and lower bounds on the optimal objective function value. While feasible solutions provide primal bounds, dual bounds are often obtained with the help of cutting planes. Cutting planes are valid inequalities for the convex hull of all integer points contained in a given polyhedron. The use of generic cutting planes is a key reason for the impressive success of today’s leading software for solving integer-programming problems.
One of the core concepts of the emerging field called “algorithmic game theory” is the price of anarchy, which measures the loss of efficiency in a system of selfish and independent agents if compared to a globally optimal, centrally coordinated solution. One of the most celebrated results is that the price of anarchy of selfish routing in a multi-commodity flow network with affine-linear link delay functions is at most 4/3, regardless of the topology of the network. There are many exciting open questions regarding the price of anarchy in a variety of other contexts.