組織

専攻

附属センター

関連連携研究機構

関連学部

Dual Integrality of the Blossom Algorithm and Its Applications（花アルゴリズムの双対整数性とその応用）

米林 悠真

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

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

双対変数と最短距離の関係
グラフが与えられた時，頂点の次数制約を超えない範囲で各枝から０本以上選んだものをb-マッチングと言う．重み付きb-マッチングの双対問題の最適解のうち整数のものを求めるアルゴリズムを提案した．また，その双対解が最短距離を表すことも示した．
修論の感想

実際に執筆を行うと，自分の理解の浅さを思い知らされ，細部まで突き詰めて考えることの大変さを痛感した．これまで知見を積み上げてきた先人たちに衷心より敬服した．

>
ISTyくん

東京大学 THE UNIVERSITY OF TOKYO

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