k-サーバ問題のトロピカル行列表現による解法

渡辺 俊大

（指導教員：平井 広志 講師／数理情報第2研究室）

研究概要

オンライン問題の一つであるk-サーバ問題の解法で現在最良の競合比をもつワーク関数アルゴリズムが，有理関数行列の積演算と最小次数をとるという操作で記述可能であることを示した．これをトロピカル化することでPseudo WFAという新たなアルゴリズムを提案し，従来解法の高速化を行った．

ワーク関数アルゴリズム(WFA)とPseudo WFAの比較

卒論の感想

研究内容に関する話題だけでなく，人に分かり易く物事を伝える技術など色々なことを学ぶことができた．困難も多々あったが有意義な研究生活が送れたと思う．