研究

オンラインマッチング問題とは

検索してもあまり日本語の資料がなかったので軽く書いておこうと思います。

概要

オンラインアルゴリズム+マッチング問題のこと。

オンラインアルゴリズム(wikipedia)

マッチング問題(ORWiki)

つまりマッチング問題をオンライン形式でやっちゃおうぜということです。

もう少し詳しく

とはいってもどうオンライン形式にするのがという話があります。

これについてはオンラインマッチング問題を提唱したAn optimal algorithm for on-line bipartite matching(Karpら, 1990)が扱ったモデルが一般的です。

これは二部マッチングで片方の頂点集合は最初から与えられていてもう片方の頂点がオンライン形式でやってくるというモデルで、一緒に辺の情報もやってきてマッチング数を最大化しようという問題です。

条件を緩める方法としてはアドバリサリの能力はもちろん、オンライン形式のモデルなどがあります。

問題としては重みつきで重みを最大化する問題であったり、頂点に容量があって重みを最大化する問題であったり、両方の頂点をオンライン形式で扱う問題であったりといろいろあります。

そのあたりの発展についてはまた気が向いたら記事にしようと思います。

まとめ

とりあえず今回は

  • オンラインマッチング問題はマッチング問題をオンライン形式でやるやつ
  • 片方の頂点集合が事前に分かっていてもう片方がオンライン形式で来るモデルが一般的

ということだけ伝えられたら満足です。

参考

An optimal algorithm for on-line bipartite matching(Karpら, 1990)

Online Matching and Ad Allocation(Aranyak Mehta, 2012)