Mathematical Optimization
The Mathematical Optimization group’s reasearch focus is on online optimization, approximation algorithms, and algorithmic game theory. In online optimization, problem data arrives piecewise (online) and needs to be processed before the full input is known. The goal is to find algorithms that work well in this setting, which occurs in many practical problems. For example orders arriving at a factory. The factory needs to start producing output (create a schedule for its machines) before the day is over and everybody goes home without having produced any output.
We compare so-called online algorithms to the offline solution, which can only be determined by knowing the whole input in advance. A classic example of an online problem is online bin packing. In this problem, items with sizes between 0 and 1 arrive online and need to be packed into bins of size 1. The goal is to minimize the number of bins used. This is a problem with many practical applications. Higher dimensional versions of this problem have also been studied (by us and by others).
A related area is approximation algorithms. These are used in cases where the full input is known in advance, but we do not have an efficient method to calculate an optimal solution. For instance, if the problem is NP-hard. Again, bin packing is a prime example. In fact, bin packing was one of the first problems for which approximation algorithms and online algorithms were developed.
The third main area we are interested in is algorithmic game theory. This area delas with problems involving selfish agents, which occur in many settings. Typically, the agents are only interested in their own profit, and our goal is to design a new system (a mechanism) which leads these agents to cooperate with the systems and produce good results.