組織

専攻

附属センター

関連連携研究機構

関連学部

多重マトロイド制約最適化問題の近似アルゴリズムと整数性ギャップ

腰高 拓美

（指導教員：岩田 覚 教授／ 数理情報第7研究室）

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

先行研究の拡張
三つ以上のマトロイドを制約条件とする最適化問題に対して, 重みなしの場合は先行研究の線形計画緩和を用いた近似アルゴリズムを適用できることを示した. また重みつきの場合もマトロイドのクラスを制限した場合は同様の整数性ギャップを持つことを示した.
修論の感想

研究が上手くいかないことも多く, 研究の難しさを実感しましたが, 無事に論文を書き上げることができ, 有意義な２年間を過ごすことができました.

>
ISTyくん

東京大学 THE UNIVERSITY OF TOKYO

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