Matroid Partition Property and the Secretary Problem

on YouTube ↗25m

" summary

Proves that no algorithm which first reduces a matroid to a partition matroid (possibly after sampling a beta fraction) and then runs the standard secretary routine achieves a constant competitive ratio for all matroids: constructs the complete binary matroid Bd and shows any partition reduction concentrates almost all elements into O(sqrt d) parts, so the best reduction-based algorithm has competitive ratio at most about d^{-1/4} and thus vanishes as d grows.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 6:54Outline of the Rest of the Talk
3. 7:33Matroid Secretary Problem: Partition Matroids
4. 8:33Matroid Partition Property
5. 10:03Matroid Secretary Problem: Graphic Matroids
6. 12:14Partition Reduction Based Algorithms
7. 14:26Complete Binary Matroid
8. 16:19Proof of Main Theorem
9. 23:53Conclusion
10. 24:18Open Problems (Beside the Obvious One!)