Fast matroid intersection and applications

by Francisco Miguel Enxerto Sena

MSc thesis presentation and discussion.

Date: 2022-Jun-17   Time: 10:30
Room: Zoom

Abstract: Matroids are a very useful abstraction in mathematics and
combinatorial optimization allowing to model many different problems, such as
optimal spanning trees, optimal arborescences, and optimal assignments.
General-purpose algorithms can then be used to solve instances of many
different problems. The issue with these general algorithms is that their
complexity is usually higher than that of problem specific algorithms. One of
those general algorithms is the matroid intersection algorithm, which also
plays an important role in other general matroid algorithms.

The aim of this work is to study a new implementation of the matroid
intersection algorithm based on recent techniques proposed from a theoretical
point of view. Those techniques might allow us to obtain a general
intersection algorithm with a complexity closer to that of problem specific
algorithms. Hence, exact and approximate algorithms will be implemented and
evaluated for their practical applicability on different problems.