Date：2024/09/27 14:20-15:30
Location：CSIE R103
Speakers:Prof. Shang-En Huang,NTUCSIE
Host: Prof. Chu-Song Chen
Abstract
Graph matching is one of important mathematical objects in graph theory.
It models relationships in scenarios such as matching advertisements to customers, students to dorm rooms, or organ donors to recipients. Most natural applications to graph matchings are bipartite, that is, the entities between the two parties are from different groups. However, matchings within the same group of entities are also useful. For example, algorithms for maximum weighted matching are used as subroutines in problems such as the Chinese postman problem and the traveling salesperson problem.
Several efficient algorithms have been developed for various bipartite graph matching problems, yet only a few solve general graph matching problems, let alone in the distributed computation models such as the CONGEST model. The CONGEST model is a vertex-centric distributed computation model that models a bounded bandwidth network. In this talk, I will first divert a bit and briefly introduce some algorithmic applications to graph matchings: (1) the sorting network, and (2) the cut-matching game of constructing expanders in the CONGEST model. These two ideas lead to a recent project I have joined on the routing problem in expander graphs. Then, I will introduce a previous project I have joined on computing an approximate maximum weighted matching in the CONGEST, parallel, and semi-streaming model.
This talk is based on the following two papers:
[1] Yi-Jun Chang, Shang-En Huang, Hsin-Hao Su, "Deterministic Expander Routing: Faster and More Versatile", The ACM Symposium on Principles of Distributed Computing (PODC), 2024.
[2] Shang-En Huang, Hsin-Hao Su, "(1-ε)-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings", ArXiv, 2023. Note: its preliminary version appeared in PODC 2023.
Biography
Shang-En Huang is currently an assistant professor in the Department of Computer Science and Information Engineering (CSIE), National Taiwan University. Previously, he had the honor of being advised by Seth Pettie and obtained his Ph.D. degree from University of Michigan. He then became a postdoc at Boston College advised by Hsin-Hao Su. Shang-En's research interests include dynamic graph data structures and algorithms and distributed graph algorithms.