Finite Playground

To verify is human; to prove, divine.


3 Comments

Maximum matching in general graphs

首先, FOCS ’11 的 accepted paper list 出來(好幾天)了. 有 pdf 的版本在此. 今年有許多圖論演算法的論文在其中, 很多令人振奮的好結果!

今天想要來講一篇新出爐的, 一個令人驚訝的圖論演算法結果! 我們都知道所謂的 Maximum matching 問題: 給定一張圖, 求上面最大的 matching 的大小. 這個問題在 bipartite graph 上有 Hopcroft-Karp 利用 augmenting path 的O(m\sqrt{n})演算法. 這被 Micali-Vazirani 推廣到了 general graph 上, 改進了標準的 Edmonds 開花演算法. 在這之後 Mucha-Sankowski 利用 Gaussian Elimination 及矩陣相乘作到了 randomized O(n^\omega) time.

前兩天, 來自印度資訊科技學院的 Jindal, Kochar 和 Pal 在 Arxiv 上公布了這篇 Maximum Matchings via Glauber Dynamics, 宣稱他們將 maximum matching in general graphs 改進到了 randomized O(m\log^2 n) time, 是第一個 near linear-time 的演算法! 使用的技巧是最近正夯的 Glauber Dynamics, 分析稍微複雜, 但演算法卻是簡單的驚人!

RandMatching(G), G 為 n-node m-edge graph.
1. 令M_0為任意 matching. 令p = 2^m.
2. 執行底下迴圈k=10m \log n次, 迴圈參數為i:
  2.1 隨機選取一個邊e.
  2.2 令M'\frac{p}{1+p}的機率是M_i \cup \{e\}, 有\frac{1}{1+p}的機率是M_i \setminus \{e\}.
  2.3 假如M'是個 matching, 則令M_{i+1} = M'; 不然就還是讓M_{i+1} = M_i.
3. 輸出M_k, 程式結束.

簡單來說, 根本就是隨便亂選邊, 然後隨機加進去或是拿掉, 然後作了夠多次之後就宣稱輸出的結果有很大的可能性就是一個 maximum matching!! 實在是太不可思議了… 對隨機演算法或是圖論演算法有興趣的人, 這是個必看的結果!

Advertisements