Goemans & Williamson

Goemans & Williamson の Max-cut への SDP 緩和についての論文を読む。

Goemans and Williamson: "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming", Journal Of ACM, 42(6), 1995, 1115-1145

「SDP緩和が NP-hard な問題に利用できる」ということを証明した論文であって、やはり SDP 緩和の証明の基本でもある。
特に、Lemma 3.2 の確率に関する系が数学的に重要で、あとはこれのアレンジである。

あと、Lovasz の論文に strongly self-dual という概念があったので、これについても調べてみようと思うが、明日は別の論文を読む予定なので、さらにあとになるかもしれない。



他に、SDPA のソースを Debian だけでなく、Ubuntu でもコンパイルした。
Debian と Ubuntu では gcc のバージョンが違うためか、どちらかで warning にならなくても、もう一方で warning となるケースがある。
（現時点で gcc のバージョンでは Debian-unstable のもののほうが Ubuntu-10.04 のものより新しい）

今日の作業内容：SDPA コンパイル 3h + 論文読み 3h
今日のBGM: EVA OST [1,2]
今日のランチ：信華園 マーボー春雨
明日の予測作業時間：5h