研究

「Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching」を読みました

概要

論文

Karpの論文でなされていたランキングアルゴリズムの性能解析がとても難しい(僕も実はよく理解できていない)ので、それをもっとシンプルに証明しようとした論文が複数あり、この論文もそのうちのひとつ。

ただしその手法がとても汎用性が高く、もっとも基本てきなオンライン二部マッチングだけでなく重み付きや予算付きなどの解析にも応用できる手法ということが述べられている。

ポイントはプライマルデュアル法の双対問題の制限も確率的に変えることでよりシンプルに解析ができるという点。

感想

正直なところよく理解できていません…

英語が苦手なのでそもそも証明で用いられている設定をきちんと理解できているかが怪しいというのが大きな問題。

ただ得るものはありましたし、読まないといけない論文や勉強しないといけない手法を認識できた点は良かったと思います。

もう少し賢くなってから読み直したいと思います。