My main research interests lie in combinatorial optimization and in particular, polyhedral combinatorics. Currently, we are investigating the integrality gap of certain linear programming formulations, which measures how well the polyhedron corresponding to the linear relaxation is approximating the integral version of the problem. In our ongoing project, we are focusing on the restricted assignment problem with the configuration - LP relaxation, which seems to be the most attackable among the problems admitting an unknown integrality gap. Our results are currently under review at ESA 2026.
In parallel, we discovered an interesting connection between two seemingly distant areas of combinatorial optimization: approximation algorithms and the branch-and-bound framework. In a recent work, we showed that under some specific circumstances, the B&B framework can be viewed as a Polynomial-Time Approximation Scheme (PTAS). The extended version of our paper was later published at Math. of OR.
Apart from my main line of research, I'm also interested in the broader are of discrete mathematics and graph theory. During a summer project as part of my MSc studies, we have generalized a classical concept in extremal graph theory and determined the corresponding extremal number for a large class of graphs. I served as an area expert for graph theory in the project QEDBench, which aimes to develop a benchmark for evaluating the mathematical reasoning abilities of large language models. The work has been accepted at ICML 2026.
Feel free to reach out to me in case you wish to start a collaboration, or simply have questions regarding our work!
Encz, K., Marits, M., Váli, B., & Weisz, M. (2024). Results on Extremal Graph Theoretic Questions for Q-Ary Vectors. Studia Scientiarum Mathematicarum Hungarica, 61(1), 30-42.
Encz, K., Mastrolilli, M., Vercesi, E. (2025). Branch-and-Bound Algorithms as Polynomial - Time Approximation Schemes. ICALP 2025.
Encz, K., Mastrolilli, M., Vercesi, E. (2025). Branch-and-Bound Algorithms as Polynomial - Time Approximation Schemes. Math. of OR.