令和4年度 九州大学システム情報科学府
与えられる入力に対して何らかの出力を行うのが算法(algorithm)の最も基本的な姿ですが、一度限りの問答ではなく、刻々と少しずつ明かされる入力にその場その場で答えてゆく応対(online)型の問題もあります。本講義ではそのような応対最適化問題を幾つか取り上げ、その算法の評価尺度である競合比(competitive ratio)の解析手法について紹介します。