1 0 0 0 OA 大規模データ処理に向けたアルゴリズム設計理論の展開
1.最小コスト木被覆問題・有向シュタイナー木問題・有向木被覆問題・b辺支配集合問題などのNP困難なグラフやネットワーク上での組合せ最適化問題に対し,新たに近似アルゴリズムを設計し,従来からの近似保証を改善した.2.侵入者と守衛の間で行われるグラフ護衛ゲームにおいて,最小の守衛数を求める問題に対し,従来手法を拡張し,侵入者が木上を移動する場合でもΘ(log n)倍以下で近似可能であることを示した.3.多状態スキーレンタル問題について,いかなるインスタンスに対し最適戦略をとっても,競合比はe/(e-1)より小さくできないことを示した.
1 0 0 0 OA 効用関数を導入したオンライン最適化問題に関する研究
本研究では効用関数の考え方を応用したオンライン最適化問題を考察する。ミクロ経済学では、次元の異なる量を組み合わせて効用関数が定義されている。しかし、アルゴリズムの性能評価尺度としてはほとんど使われてこなかった。我々は、制約条件として扱われていたものを目的関数に取り入れたり、性能評価尺度の期待値を目的関数としたりして問題再設定を行う。結果、一方向通貨交換問題に対しては、どのような効用関数の設定をするかに依存して最適戦略が大きく変わってくることを実証できた。また、オンライン・オフライン混合ジョブスケジューリング問題に対しては実用的かつ頑強なアルゴリズムが得られた。