Explore a 23-minute IEEE conference talk on faster matroid intersection algorithms. Delve into exact algorithms, including the augmenting path method and shortest augmenting path (SAP) for matroid intersection. Discover challenges and innovative solutions like binary search. Examine approximate algorithms, augmenting path and set concepts, and the equivalence theorem. Gain insights from experts Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong as they present their novel approach to this complex mathematical problem.
Overview
Syllabus
Faster Matroid Intersection
Roadmap
Exact Algorithms
Augmenting Path Method
Shortest Augmenting Path (SAP) for Matroid Intersection
SAP for Matroid Intersection
Challenge
Idea 1: Binary Search
Summary
Approximate Algorithm
Augmenting Path Augmenting Set
Equivalence Theorem
Our Algorithm
Taught by
IEEE FOCS: Foundations of Computer Science
