2025.08.12, Chien-Chung Huang, Robust Sparsification for Matroid Intersection with Applications
Автор: IBS Discrete Mathematics Group
Загружено: 2025-08-12
Просмотров: 124
Chien-Chung Huang, Robust Sparsification for Matroid Intersection with Applications
August 12 Tuesday @ 4:30 PM - 5:30 PM KST
Room B332, IBS (기초과학연구원)
Chien-Chung Huang
CNRS, DI ENS, PSL
https://www.di.ens.fr/~cchuang/
The matroid intersection problem is a fundamental problem in combinatorial optimization. In this problem we are given two matroids and the goal is to find the largest common independent set in both matroids. This problem was introduced and solved by Edmonds in the 70s. The importance of matroid intersection stems from the large variety of combinatorial optimization problems it captures; well-known examples in computer science include bipartite matching and packing of spanning trees/arborescences.
In this talk, we introduce a “sparsifer” for the matroid intersection problem and use it to design algorithms for two problems closely related to streaming: a one-way communication protocol and a streaming algorithm in the random-order streaming model.
This is a joint-work with François Sellier.
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
