オンライン最小採択確率最大化ナップサック問題の解析

善永 徹

(指導教員:河瀬 康志 特任准教授/数理情報第2研究室

資料PDF(yoshinaga.pdf
研究概要

逐次的に到着するアイテムの処理例
逐次的に与えられる確率的なサイズをもつアイテムを,アイテムが与えられるたびにナップサックへ詰め込むか判断するオンラインナップサック問題について解析する.アイテムのサイズ分布は到着時に判明し,アイテムサイズの実現値はナップサックに詰め込んだ直後に確定する.この問題の目的は,容量制約を満たしつつ,どのアイテムもナップサックに入れられる確率が一定以上となるアルゴリズムの設計である.
修論の感想

数理工学に関するバックグラウンドが乏しい筆者でしたが,修士論文の完成までたどり着けました.指導教員の河瀬康志先生のお力添えの賜物です.


>
ISTyくん