Zusammenfassung für den Vortrag am 13.12.2017 (10:30 Uhr)


Sarah Berkemer (MPI MIS, Leipzig + IZBI)
An introduction to greedoids

A greedy strategy to tackle a given problem involves only locally optimal choices and no backtracking. In 1980, Korte and Lovász noticed that many instances where such a strategy is optimal can be described by a combinatorial object which generalizes matroids: such an object is now known as a greedoid. In this survey talk weintroduce the concept of greedoid (with many examples from graph theory), draw a comparison to matroids and focus on some combinatorial optimization aspects.


06.06.2018, 07:23