Hi, we are G²OAT research group

The G²OAT research group focuses on research in discrete optimization. The main focus of the group is in computational and combinatorial problems that arise (mostly in) graph theory, game mechanisms, cooperative and non-cooperative games, and computational social choice theory. We design efficient algorithms for these problems. We use means of classical complexity theory, parameterized complexity, graph theory, or, e.g., integer linear programming.

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 is 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.