情報処理学会 第82回全国大会 会期:2020年3月5日~7日 会場:金沢工業大学 扇が丘キャンパス 情報処理学会 第82回全国大会 会期:2020年3月5日~7日 会場:金沢工業大学 扇が丘キャンパス

7L-01
直線上の2サーバーオンラインマッチング問題に対する貪欲アルゴリズムの競合比解析
○佐竹 誠,宮崎修一(京大)
直線上のオンライン二部マッチング問題(Online Matching on a Line; OML)とは、事前に与えられたサーバー集合とオンライン形式で与えられるリクエスト集合に対してマッチング間の距離の和を最小化する問題である。現在OMLの競合比は上下限に大きな開きがある。そこで本論文では、OMLに制限を加えたモデルでより良い競合比を示すことを目的として、サーバーの位置が2箇所であるようなモデルを考察する。このモデルに対して貪欲アルゴリズムが競合比3を達成し、かつ任意の決定性アルゴリズムが3以上の競合比を持つことを示す。