Weighted linear matroid parity問題

01-29

今年的STOC best papers之一是Satoru Iwata和Yusuke Kobayashi的文章. A weighted linear matroid parity algorithm.

這個實際上2011年Pap和Iwata都獨自說已經有演算法了, 但是花了這麼多年才把paper寫出來... Pap的文章還沒有發出來... 有興趣的可以去看那個快60頁紙的technical report, 全是演算法的描述和證明. http://www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2017/METR17-01.pdf

那麼什麼是weighted linear matroid parity(也叫matroid matching)問題, 為什麼這文章可以拿STOC best paper呢?

Input: 給一些集合 $S_1,ldots,S_n$ . 每個集合里有兩個向量(任何域都可以). 集合 $S_i$ 有weight $w(S_i)$ . 讓 $S=bigcup_{i=1}^n S_i$ .
Output: 找到 $Xsubset [n]$ , 使得
1. 對於任意 $i, jin X$ , $ineq j$ ,不存在向量同時存在於 $S_i$ 和 $S_jn$ 中.
2. $bigcup_{iin X} S_i$ 是 $Sn$ 的一個基.

3. 滿足上訴兩個條件的 $X$ 下 $sum_{i in X} w(S_i)$ 最小.

一個演算法問題, 見得多了之後, 感覺如果有多項式時間演算法, 也就那幾種.

一般的設計方法, 自然是演算法課上的那些常見的設計方法. DP啊, Greedy啊這些常見的小鎚子. 不行的話, 就要開始拿稍微強勁一點的鎚子來砸了.

有兩個稍微常見的鎚子

- min-cost (integral) flow

- max weight matching

這兩個鎚子在無向圖上都可以規約到一個更高端的問題, 最大weight的vertex disjoint S-path問題.

給一個圖G=(V,E), 以及一個一些特殊的頂點 $Tsubset V$ . $T$ 被partition為 $mathcal{S}={S_1,ldots,S_k}$ , 其中 $S_isubset V$ . 每個邊上有一個weight. 一個path叫做 $mathcal{S}$ -path, 如果這個path的起點屬於 $S_i$ , 終點屬於 $S_j$ , 中間不通過任何其他 $T$ 裡面的頂點.

$mathcal{S}$ -path問題: 找到一些vertex disjoint的S-paths, 使得weight的和最大.

這個看起來非常NP-hard的問題可以規約到weighted linear matroid parity問題上. 而Iwata和Kobayashi的這個文章就解決了這個問題, 給了我們可以合二為一的大鎚子. 現在我揮舞著這個鎚子會想我以前的哪些釘子/手機可以用這個來敲...

最近在日本這邊交流, 和上訴的作者都見過面聊了聊. 我在想的幾個問題被告知是一些我聽都沒有聽過的問題的特殊版本. 不愧是(理論的)組合優化強國啊.