Subsampling Semidefinite Programs and Max-Cut on the Sphere

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
http://arxiv.org/abs/0911.5526

計算量理論の研究者がSDPの研究をしているということを最適化の研究者はあまり知らないと思う．もちろん最適化の研究者は実際の計算に興味のある場合が多いが，一方，計算量理論の研究者は出現するSDPを解析することに興味がある，という点で立場の違いは見える．
この話の出発点はGoemans-Williamsonによる最大カット問題に対する近似アルゴリズムであり，その偉大さが分かる．これについては中大の松井先生がOR学会誌に書いた解説が10年程経ったいまでも素晴らしい．
その後，unique games conjectureとかmetric embeddingの研究の進展があって，SDPがこのような問題の本質に深く関わっていることが分かってきた．また，そこには量子計算量理論も絡まってきているらしい．これらはどれも離散アルゴリズムの研究であるのに，その手法や背後にある思想は高次元離散幾何であるということは重要である．

さて，この論文はぱっと見たところ，Goemans-WilliamsonのSDP緩和を作るときに小さなランダム標本から作っても最適値がほとんど変わらないということを示している．これが任意の(正則)グラフに対して成り立つというのだからすごい．こういう話は密なグラフに対しては成り立つということが知られていたが，それが疎であってもよいということらしい．