一般圖上的 (1-ε)-近似最大帶權匹配
- 講者黃上恩 博士 (波士頓學院)
邀請人：蔡孟宗 - 時間2023-07-28 (Fri.) 10:00 ~ 11:30
- 地點資訊所新館106演講廳
摘要
一般圖上的最大帶權匹配問題 (Maximum Weighted Matching, MWM) 是組合最佳化中一類非常經典的問題。由於這個問題在找出最佳解的要求時不易平行化，因此在分散式計算模型 (如LOCAL 與 CONGEST 模型) 中，近年的研究方向轉為有效率地找出 (1-ε)-近似解。
在今天的演講中，我們將簡短地討論若干尋找 (1-ε)-近似最大帶權匹配的演算法。接著，我將會介紹我們在 CONGEST 分散式計算模型中的 (1-ε)-近似最大帶權匹配演算法，其所需的執行輪數 (round complexity) 為 poly(1/ε, log n)。此演算法應用在平行計算模型 (PRAM) 與串流式計算 (Semi-Streaming) 中，也能在理論上有所突破。詳情請參考 https://arxiv.org/abs/2212.14425。
在今天的演講中，我們將簡短地討論若干尋找 (1-ε)-近似最大帶權匹配的演算法。接著，我將會介紹我們在 CONGEST 分散式計算模型中的 (1-ε)-近似最大帶權匹配演算法，其所需的執行輪數 (round complexity) 為 poly(1/ε, log n)。此演算法應用在平行計算模型 (PRAM) 與串流式計算 (Semi-Streaming) 中，也能在理論上有所突破。詳情請參考 https://arxiv.org/abs/2212.14425。