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