数解研の谷川さんとやっていた研究がAlgorithmicaに通った。関数f:2^V->Zでcrossing supermodularなものが与えられた時に、グラフのカットがこの関数fを満たしているかを定数時間で検査する話。二泊三日の出張で完成した簡単な話だけど一般的で良い。
YOSHIDA Yuichi retweeted
SODAに論文が通りました.吉田さんと岡君との共著で,グラフからk点除去して二部グラフにする問題や,max2SATで高々k個以外の節を充足する問題などを O(4^k (n+m)) 時間で解くアルゴリズムです.
YOSHIDA Yuichi retweeted
会社ブログ書きました。今週開かれたSIGKDDのベストペーパーの行列スケッチアルゴリズムを実装してGithubで公開してます。PCA近似の実験サンプル付き。 "今年のSIGKDDのベストペーパーを実装・公開してみた" research.preferred.jp/2013/0…


