(1-ε)-Approximate Maximum Weighted Matching in Parallel, Distributed, and Semi-Streaming Settings
- LecturerDr. Shang-En Huang (Boston College)
Host: Meng-Tsung Tsai - Time2023-07-28 (Fri.) 10:00 ~ 11:30
- LocationAuditorium 106 at IIS new Building
Abstract
The problem of computing the maximum weighted matching (MWM) on an undirected weighted graph is one of the fundamental combinatorial optimization problems. In distributed graph algorithms such as CONGEST and LOCAL, solving exact MWM requires Ω(D) rounds, where D is the diameter of the graph. To get around with this diameter barrier in the network, approximated solutions are considered.
In this talk, I will first give a brief overview for solving the (1-ε)-Approximate MWM problem in the sequential setting. In particular, I will introduce very briefly three different approaches to solve the MWM problem on bipartite graphs (Zheng and Henzinger 2023), and on general graphs (Duan and Pettie 2014), (Assadi 2023). Then, I will present our (1-ε)-Approximate MWM algorithm that runs in poly(1/ε, log n) rounds in the CONGEST model.
In this talk, I will first give a brief overview for solving the (1-ε)-Approximate MWM problem in the sequential setting. In particular, I will introduce very briefly three different approaches to solve the MWM problem on bipartite graphs (Zheng and Henzinger 2023), and on general graphs (Duan and Pettie 2014), (Assadi 2023). Then, I will present our (1-ε)-Approximate MWM algorithm that runs in poly(1/ε, log n) rounds in the CONGEST model.