Algorithms for matching problems
Event details
| Date | 12.07.2022 |
| Hour | 13:00 › 15:00 |
| Speaker | Weronika Wrzos-Kaminska |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
Matching theory is one of the fundamental topics in the area of combinatorial optimization. Not only does it have a wide range of applications, but it has also played an important role in the development of algorithmic techniques. In this report, we will focus on recent algorithms for matching problems in the online and streaming models. First, we will discuss Bernstein's elegant algorithm for the random-order semi-streaming model. Then, we will discuss the breakthrough by Fahrbach, Huang, Tao, and Zadimoghaddam, who gave the first non-trivial algorithm for the edge-weighted online bipartite matching problem. Finally, we discuss the recent work by Huang, Shu and Yan, who study the online stochastic bipartite matching problem under general arrival rates.
Background papers
1.Improved Bounds for Matching in Random-Order Streams (ICALP 2020)
by Aaron Bernstein
https://arxiv.org/pdf/2005.00417.pdf
2. Edge-Weighted Online Bipartite Matching (FOCS 2020)
by Matthew Fahrbach, Zhiyi Huang, Runzhou Tao and Morteza Zadimoghaddam
https://arxiv.org/pdf/2005.01929.pdf
3. The Power of Multiple Choices in Online Stochastic Matching (STOC 2022)
by Zhiyi Huang , Xinkai Shu and Shuyi Yan
https://arxiv.org/pdf/2203.02883.pdf
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
Matching theory is one of the fundamental topics in the area of combinatorial optimization. Not only does it have a wide range of applications, but it has also played an important role in the development of algorithmic techniques. In this report, we will focus on recent algorithms for matching problems in the online and streaming models. First, we will discuss Bernstein's elegant algorithm for the random-order semi-streaming model. Then, we will discuss the breakthrough by Fahrbach, Huang, Tao, and Zadimoghaddam, who gave the first non-trivial algorithm for the edge-weighted online bipartite matching problem. Finally, we discuss the recent work by Huang, Shu and Yan, who study the online stochastic bipartite matching problem under general arrival rates.
Background papers
1.Improved Bounds for Matching in Random-Order Streams (ICALP 2020)
by Aaron Bernstein
https://arxiv.org/pdf/2005.00417.pdf
2. Edge-Weighted Online Bipartite Matching (FOCS 2020)
by Matthew Fahrbach, Zhiyi Huang, Runzhou Tao and Morteza Zadimoghaddam
https://arxiv.org/pdf/2005.01929.pdf
3. The Power of Multiple Choices in Online Stochastic Matching (STOC 2022)
by Zhiyi Huang , Xinkai Shu and Shuyi Yan
https://arxiv.org/pdf/2203.02883.pdf
Practical information
- General public
- Free
Contact
- edic@epfl.ch