組織

専攻

附属センター

関連連携研究機構

関連学部

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

善永　徹

（指導教員：河瀬 康志 特任准教授／数理情報第2研究室）

資料PDF（yoshinaga.pdf）
研究概要

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

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

>
ISTyくん

東京大学 THE UNIVERSITY OF TOKYO

Copyright © 2019 　Graduate School of Information Science and Technology, The University of Tokyo