Efficient Algorithms for (1-ε)-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings

Abstract:
Given an undirected weighted graph G, finding the maximum weighted matching (MWM) on G is one of the most classic combinatorial optimization problems. In distributed graph algorithms (such as CONGEST and LOCAL models), solving MWM exactly 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 (Ahn and Guha 2011), (Zheng and Henzinger 2023), and on general graphs (Duan and Pettie 2014). Then, I will present our (1-ε)-Approximate MWM algorithm that runs in poly(1/ε, log n) rounds in the CONGEST model.

Bio:
Shang-En Huang is currently a postdoc in Boston College. His current research interests include distributed graph algorithms and dynamic graph algorithms. He obtained his PhD from University of Michigan. Besides his research interests, he is also interested in competitive programming. He co-coached programming teams at the University of Michigan and at Boston College.