27/05/2025 - 15:00 - CORE B.-135 
> "Matroids: optimization and polyhedra". 

Emiliano Lancini (Université Paris-Dauphine) 
will give a presentation on : 

Matroids: optimization and polyhedra. 

Abstract : 

In this lecture, I will present a key optimization result concerning matroids. We will begin by recalling the standard definition of a greedy algorithm and then demonstrate that greedy algorithms yield optimal solutions for every linear maximization or minimization problem over a combinatorial structure if and only if that structure is a matroid. This result will be illustrated through a classical example: Kruskal's algorithm. We will then introduce a related polyhedral object, the polymatroid, and discuss some of its fundamental properties, including box-total dual integrality.