論文概要
弊研究室の准教授の論文。
オンラインの安定結婚問題を考えた時に、どうがんばってもブロッキングペアができてしまうことは証明されている。そのためこの問題自体を考えるのはあまりおもしろくない。
そこでこの問題がどれくらい難しいのかということをオンラインアルゴリズムにオラクルがアドバイスを与えるという設定を用いて測る。
論文ではlog(n!)ビットのアドバイスがあればオンラインでも完全マッチングが構築できると結論づけている。
感想
そもそもオンラインで安定結婚問題を考えるというのが初めて知ったアプローチでしたし、必ずブロッキングペアができてしまうという結論もショッキングでした。
本論文ではそこから踏み込んでその難しさを測っていてそこを調べるのが研究っぽくて好きです。
難しい問題を条件を緩めて詳しく調べるというのは便利な手法だなあと思いました。
例えばオンラインアルゴリズムでもう一つ先のインプットまで見てから決定できるとかういった論文もあるのかなあと気になりました。
