What we do
We propose exact polynomial, parameterized, moderately exponential algorithms, and approximation algorithms. We design new combinatorial games, whose equilibria represent an efficient solution to a given problem. We present lower bounds for time complexity of any algorithm solving a problem at hand. These typically show that the algorithms achieve asymptotically optimal running times, often in the fine-grained complexity perspective. The research of our group also includes purely combinatorial results, i.e., describing properties of objects or relationships between them, for example in the field of Ramsey’s theory.
The problems we solve are all the discretely modelled optimization problems. These are a wide range of problems – from graph problems across scheduling or social choice to strategies for combinatorial games. In a number of algorithms, we use results related to integer linear programming.
