BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Algorithms for matching problems
DTSTART:20220712T130000
DTEND:20220712T150000
DTSTAMP:20260406T064557Z
UID:f92042a4952a1e048eb9bbda419d506db3ee229fe831df6800e9692b
CATEGORIES:Conferences - Seminars
DESCRIPTION:Weronika Wrzos-Kaminska\nEDIC candidacy exam\nExam president: 
 Prof. Mika Göös\nThesis advisor: Prof. Michael Kapralov\nCo-examiner: Pr
 of. Ola Svensson\n\nAbstract\nMatching theory is one of the fundamental to
 pics in the area of combinatorial optimization. Not only does it have a wi
 de 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-ord
 er semi-streaming model. Then\, we will discuss the breakthrough by Fahrba
 ch\, Huang\, Tao\, and Zadimoghaddam\, who gave the first non-trivial algo
 rithm for the edge-weighted online bipartite matching problem. Finally\, w
 e discuss the recent work by Huang\, Shu and Yan\, who study the online st
 ochastic bipartite matching problem under general arrival rates.\n\nBackgr
 ound papers\n1.Improved Bounds for Matching in Random-Order Streams
  (ICALP 2020) \nby Aaron Bernstein\nhttps://arxiv.org/pdf/2005.00417.pdf
 \n\n2. Edge-Weighted Online Bipartite Matching  (FOCS 2020)\nby Matthew 
 Fahrbach\, Zhiyi Huang\, Runzhou Tao and Morteza Zadimoghaddam\nhttps://ar
 xiv.org/pdf/2005.01929.pdf\n \n3. The Power of Multiple Choices in Online
  Stochastic Matching (STOC 2022)\nby Zhiyi Huang \, Xinkai Shu and Shuyi 
 Yan\nhttps://arxiv.org/pdf/2203.02883.pdf
LOCATION:ELD 020 https://plan.epfl.ch/?room==ELD%20020
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR