電子情報通信学会ソサイエティ大会講演要旨
BS-3-4
スパースモデリングによる最小リンクフロー問題の解法に関する一検討
◎松尾涼太郎・中村 遼・大崎博之(関西学院大)
スパースモデリングと呼ばれる、モデルの特徴量が有するスパース性を
利用することで、少数の観測値からモデルの未知の特徴量を推定する統計的手
法が注目を浴びている。我々はこれまで、ネットワークの最小リンクフロー問
題をスパースモデリングによって定式化した。最小リンクフロー問題とは、各
ノードに対するトラヒック流入 / 流出レートが与えられたときに、ネットワー
ク全体で使用するリンク数を最小化するフローを求めるという問題である本稿
では、トラヒック流入ノードおよび流出ノードが複数存在する場合の最小リン
クフロー問題が、スパースモデリングによってどの程度解けるかを調査する。
なお、トラヒックの流入および流出ノードがともに単一である時の最小リンク
フロー問題は最短経路問題と等価である。また、トラヒックの流出 / 流出ノー
ドが複数存在する時の最小リンクフロー問題はシュタイナー木問題と等価とな
る。