Non TDI Optimization with Supermodular Functions

Explore a comprehensive lecture on non-TDI optimization using supermodular functions, delivered by András Frank at the Hausdorff Center for Mathematics. Delve into the significance of total dual integrality in combinatorial optimization and its limitations in certain problem types. Examine the Supermodular covering theorem by Frank and Jordán, which has proven crucial in solving various non-TDI graph-optimization problems. Discover both established and new applications of this theorem, including degree-constrained and matroidal generalizations of the term-rank problem, root-edge constrained extensions of Edmonds' disjoint arborescences theorem, and connectivity augmentation in simple digraphs. Learn about a special framework that allows for the extension of the Supermodular covering theorem to simple digraphs, overcoming previous limitations. This in-depth talk, part of the Hausdorff Trimester Program on Combinatorial Optimization, also highlights collaborative work with Kristóf Bérczi, offering valuable insights into advanced topics in graph theory and optimization.

András Frank: Non TDI Optimization with Supermodular Functions