Matching and Clustering via Higher-Order Symmetry Breaking (Delivered in English)
- LecturerProf. Hsin-Hao Su (Boston College)
Host: Kai-Min Chung - Time2023-11-16 (Thu.) 10:15 ~ 11:15
- LocationAuditorium 106 at IIS new Building
Abstract
Abstract:
Traditional studies on symmetry breaking focus on breaking symmetries on atomic objects such as nodes or edges (e.g., the maximal independent set problem and the maximal matching problem). Their generalizations to higher-order objects have the potential to be used for solving optimization problems in distributed and parallel models. In this talk, I will discuss how such primitives play a role in our two recent results as follows:
1. A poly(1/ε, log n)-time (1-ε)-approximation algorithm for the maximum weight matching problem in the CONGEST and parallel models, with the latter using O(m) processors. The algorithm can also be adapted to the semi-streaming setting with poly(1/ε) passes.
2. A poly(log n)-depth, Õ(m^{1.5})-work, (2.4+ε)-approximation parallel algorithm for disagreement-minimization correlation clustering, where m denotes the number of positively-correlated edges.
The results above appear in PODC 2023 and SODA 2024. They are based on joint works with Nairen Cao and Shang-En Huang.
Traditional studies on symmetry breaking focus on breaking symmetries on atomic objects such as nodes or edges (e.g., the maximal independent set problem and the maximal matching problem). Their generalizations to higher-order objects have the potential to be used for solving optimization problems in distributed and parallel models. In this talk, I will discuss how such primitives play a role in our two recent results as follows:
1. A poly(1/ε, log n)-time (1-ε)-approximation algorithm for the maximum weight matching problem in the CONGEST and parallel models, with the latter using O(m) processors. The algorithm can also be adapted to the semi-streaming setting with poly(1/ε) passes.
2. A poly(log n)-depth, Õ(m^{1.5})-work, (2.4+ε)-approximation parallel algorithm for disagreement-minimization correlation clustering, where m denotes the number of positively-correlated edges.
The results above appear in PODC 2023 and SODA 2024. They are based on joint works with Nairen Cao and Shang-En Huang.