Speaker: Jakob Bossek 

Abstract: The Minimum Spanning Tree (MST) problem is the challenge of finding a tree in an edge-weighted graph that maintains connectivity of all nodes and has minimal costs among all such trees. The MST problem is a fundamental combinatorial optimization problem with countless applications, e.g., in the construction of communication networks, medical imaging, or many other areas that range from logistics via graph drawing to power grid network design. The basic single-objective version of the MST problem can  be solved efficiently, i.e., in polynomial time, e.g., by Prim's algorithm. The multi-objective MST (moMST) version though (i.e., multiple weights per edge) is NP-hard and suffers from intractability. Thus, efficient heuristics are needed to approximate the set of optimal trade-off solutions. Evolutionary Algorithms are randomised search heuristics that are among the most successful when it comes to solving NP-hard multi-objective optimization problems.In this talk I will present results from a recent publication in the evolutionary computation journal (Bossek & Grimme, 2023). In this paper we analyze the neighborhood structure of Pareto-optimal spanning trees and design several highly biased sub-graph-based mutation operators founded on the gained insights. In a nutshell, these operators replace (un)connected sub-trees of candidate solutions with locally (Pareto-)optimal sub-trees. The latter (biased) step is realized by applying Kruskal's single-objective MST algorithm to a weighted sum scalarization of a sub-graph.I will detail some runtime complexity results for the introduced operators and demonstrate results that show that the sub-graph based operators beat baseline algorithms from the literature even with severely restricted computational budget in terms of function evaluations on four different classes of complete graphs. Finally, I will give a teaser on very recent results from ongoing research on a) improving the performance of the introduced operators and b) adapt them to tackle the multi-objective degree-constraint MST (a variant of the MST-problem that is NP-hard even in the single-objective case).

Short Bio: Jakob received his bachelor degree in Statistics and diploma in Computer Science from the TU Dortmund University (Germany) in 2013 and 2014, respectively. In 2018 he finished his doctorate studies in Information Systems at the University of Münster (Germany). He held PostDoc positions at the University of Münster (Germany) and the University of Adelaide (Australia). Now he is assistant professor (Akademischer Rat) at the Chair for AI Methodology (AIM) at the RWTH Aachen University. His main field of research is evolutionary algorithms (EAs), a family of randomised search heuristics that takes inspiration from Darwinian evolution theory. In this broad field Jakob is currently particularly focused on efficient EAs for (multi-objective) combinatorial optimization problems, evolutionary diversity optimization, and quality diversity. Moreover, he also very much enjoys advancing the theoretical understanding of randomised search heuristics by proving time complexity results.