Finite Playground

To verify is human; to prove, divine.

Maximum matching in general graphs

3 Comments

首先, 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!! 實在是太不可思議了… 對隨機演算法或是圖論演算法有興趣的人, 這是個必看的結果!

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

3 thoughts on “Maximum matching in general graphs

  1. 有不少人提出了疑問. 似乎是有問題!

  2. hey, 不好意思留了個跟高深演算法問題完全不相關的留言。
    只是想跟你說我找到你了!還有,雖然我完全看不懂這些文章到底是在說什麼,不過我覺得你很棒:)

    write me!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s