電子情報通信学会ソサイエティ大会講演要旨
B-11-11
未知のネットワークの最小 p-メジアン問題に関する一考察
○津川 翔(筑波大)・大崎博之(関西学院大)
最小 p-メジアン問題は、ネットワーク中から p 個のノード (メジアンノード) を選択した時に、各ノードの需要量とそのノードから最寄りのメジアンノードまでの距離の積の総和 (総コスト) が小さくなるようなメジアンノードの組合せを求める問題である。従来の研究では、ネットワーク全体の構造を用いてメジアンノードを決定していたが、本稿ではネットワークの一部の構造のみからメジアンノードを決定する問題を検討する。実験により、Sample Edge Count と呼ばれる手法を用いて全体の 5% 程度のノードを探査するだけで、ネットワーク全体の情報を用いた場合と同程度の総コストを実現できることを示す。