Faster Matroid Intersection
Offered By: IEEE via YouTube
Course Description
Overview
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.
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
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube