研究

「An Optimal Algorithm for On-line Bipartite Matching」を読みました。

任意のオンラインマッチングの論文で登場するので読んどいた方がよさそうと思って読みました。

概要

論文リンク

オンラインマッチングという分野が初めて述べられた論文(らしい)。1990年の論文なので僕は生まれてもいない。

内容としてはオンライン二部マッチングの定義とそれに対するランキングアルゴリズムの評価となっている。

他にもグリーディアルゴリズムやアーリーアルゴリズムなどいくつかの付属的なアルゴリズムも登場している。

感想

結論自体は元祖なだけあって今まで読んだオンラインマッチングの本で読んだこともある事実でしたが、その証明はたぶん初めてだったので理解するのに苦労しました。

特にアルゴリズムのパフォーマンスの話は数式もそれなりに出てきて理解するのがやっとという感じで、自分が研究としてこんな評価ができるのかというのが少し心配になりました。