Matching and Clustering via Higher-Order Symmetry Breaking (以英文演講)
- 講者蘇信豪 教授 (波士頓學院)
邀請人：鐘楷閔 - 時間2023-11-16 (Thu.) 10:15 ~ 11:15
- 地點資訊所新館106演講廳
摘要
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.