研究

オンラインメトリックマッチング問題とは

自分の研究テーマであるオンラインメトリックマッチング問題に関する日本語資料が見当たらなかったので自分の理解している範囲で書き残しておきます。

はじめに

私の専門は分野でいうとグラフ理論にあたります(参考:グラフ理論の基礎|高校数学の美しい物語)。

オンラインメトリックマッチング問題(Online Metric Matching Problem)とはオンラインマッチング問題(Online Matching Problem)の派生問題です。

よってこの記事ではまずオンラインマッチング問題の説明をしたあと、オンラインメトリックマッチング問題の説明をします。

その後既存研究や応用例などについてもごく簡単にですが述べます。

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

オンラインマッチング問題とはオンライン問題マッチング問題を組み合わせたものです。

オンラインマッチング問題 = オンライン問題 + マッチング問題

単にオンラインマッチング問題と言うときにはマッチング問題が最大二部マッチング問題であるものを指すことが多いです。

オンライン問題とは

最初に天気と洗濯物の例を紹介します。

毎日朝起きたときに天気がわかり、明日の天気は全くわからないとします。また晴れの日は洗濯物が干せますが、雨の日は干すことができず、一度の洗濯で3日分の衣服が洗濯できるとします。このとき洗濯物が溜まりすぎないようにしながら、干す回数を最小化するという問題を考えてみます。

  • 天気は今日の天気しかわからない
  • 晴れの日は洗濯ができるが、雨の日は洗濯ができない
  • 1回の洗濯で3日分の衣服が洗濯できる
  • 洗濯物が溜まりすぎないようにしながら、干す回数を最小化する

普通に考えると、なるべく3日分の衣服をまとめて洗濯したいです。しかし例えば今日は晴れで洗濯物が2日分溜まっているとすると、明日や明後日が雨になって干せない可能性を考えると干しておいた方が良いような気もします。つまり逆に洗濯物を溜めないことを重視するなら晴れの日は毎日干した方が良いのかもしれません。

このように入力が時系列で与えられる問題をオンライン問題と呼びます。この例では「天気」という入力が時系列に沿って毎日与えれています。この問題に対して、入力が与えられるたびに意思決定を行うアルゴリズムをオンラインアルゴリズムと呼びます。この例では天気がわかるたびに「洗濯物を干すか干さないか」という意思決定を行っています。

オンライン問題:入力が時系列で与えられる問題
オンラインアルゴリズム:入力が与えられるたびに意思決定を行うアルゴリズム

ちなみにオンラインアルゴリズムの性能評価としては競合比という値を用います。

より詳細な説明は以下を参照ください。

最大二部マッチング問題とは

この問題に関してはすでにわかりやすく解説してあるページがあるので、以下のページを参照ください。

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

これらのオンライン問題と最大二部マッチング問題を組み合わせた問題がオンラインマッチング問題ということになります。具体的には最大二部マッチング問題における二部グラフの片側の頂点のみが最初に与えられていて、もう片側の頂点が1つずつ与えられるような問題になります。

オンラインマッチング問題:二部グラフの片側の頂点のみが最初に与えられていて、もう片側の頂点が1つずつ与えられるような最大二部マッチング問題

カップルの例でいえば男性のみが最初から全員揃っていて、女性が一人ずつ現れるような状況です。また女性が現れた時点でその女性に関する「付き合っても良いペア」も同時に与えられます。そして女性が現れた時点でその女性をどの男性とペアにするかを決定しなければなりません。

オンラインマッチング問題2

ちなみに事前に与えれている方の頂点をサーバー、時系列に沿って与えられる方の頂点をリクエストと呼びます。

オンラインメトリックマッチング問題

オンラインメトリックマッチング問題とは、オンラインマッチング問題のうち、マッチング問題が距離空間上の最小二部マッチング問題であるようなものです。

距離空間上の最小二部マッチング問題とは

例えば平面上に火事と消防署のポイントが与えれれていて、火事と消防署を1:1対応させつつ対応させる火事と消防署の間の距離の和を最小化するというような問題です。

距離空間最小二部マッチング

ちなみに距離空間上なので平面でなくともユークリッド空間やグラフ上でも良いです。

オンラインメトリックマッチング問題とは

オンラインマッチング問題と同じようにしてオンライン化します。

つまり消防署だけが最初にわかっていて火事が1つずつ発生するような問題です。

オンラインメトリックマッチング問題

この例は火事が順番に発生するという、通常のマッチング問題よりも現実に近いモデルになっていることがわかります。

関連事項

既存研究

代表的なものだけ紹介します。

オンラインマッチング問題に対しては決定性でRankingアルゴリズムが最適であることが示されています[参考文献1]。そこから派生した様々なモデルも存在します[参考文献2]。

またオンラインメトリックマッチング問題に対しては決定性でPermutationアルゴリズムが最適であることが示されています[参考文献3, 4]。

私は現在オンラインメトリックマッチング問題の特殊化した問題である直線上のオンラインマッチング問題について研究しており、この問題に対してはまだ最適なアルゴリズムは示されていません。

代表的な応用例

オンラインマッチング問題(の派生問題)は検索エンジンの広告表示などに応用されています。オンラインメトリックマッチング問題はカーシェアリングシステムや複数ロボット間でのタスク割当などに応用されています。

最後に

なんとなくオンラインメトリックマッチング問題について雰囲気を掴んでいただけたなら嬉しいです。もし興味を持っていただけたなら参考文献として挙げている論文などを読むととてもおもしろいと思います。

誤字誤謬・質問疑問などあればTwitterまでお願いします。

参考文献

  1. An optimal algorithm for on-line bipartite matching (Karp, et al. | 1990)
  2. Online Matching and Ad Allocation (Mehta | 2012)
  3. Online Weighted Matching (Kalyanasundaram and Pruhs | 1993)
  4. On-line algorithms for weighted bipartite matching and stable marriages (Khuller, Mitchell and Vazirani | 1994)