マッチング問題に対する行列スケーリングの研究

井上 恭輔

(指導教員:平井 広志 准教授/数理情報第2研究室

資料PDF(inoue.pdf
研究概要

本研究で提案したアルゴリズム
零行および零列が存在しない非負正方行列の各行と各列を交互に正規化する手法を行列スケーリング(Sinkhorn 1964)という.本研究ではLinialら(2000)による行列スケーリングを用いた二部グラフにおける完全マッチングの存在判定アルゴリズムを改良し,反復回数などを実験的に考察した.
修論の感想

提案手法の正当性を示す行列スケーリングの収束性が予想となっていることなど未完全のままとなった部分もありましたが,研究自体はパズルを解くといったような感じで楽しかったです.


>
ISTyくん