Graphs, Games, Optimization, Algorithms, Theoretical Computer Science (G²OAT)

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

The group’s activities are focused on these topics

Contact person

RNDr. Ondřej Suchý, Ph.D.

Where to find us

Graphs, Games, Optimization, Algorithms, Theoretical Computer Science Research Group
Department of Theoretical Computer Science
Faculty of Information Technology
Czech Technical University in Prague

Building A, 12th floor
Thákurova 7
Prague 6 – Dejvice
160 00

The person responsible for the content of this page: doc. Ing. Štěpán Starosta, Ph.D.