講演抄録/キーワード |
講演名 |
2019-01-18 11:20
不完全なネットワークにおける最小p-メジアン問題 ~ 定式化と実験的評価 ~ ○津川 翔(筑波大)・大崎博之(関西学院大) CQ2018-85 |
抄録 |
(和) |
最小 $p$-メジアン問題は、ネットワークの中から $p$ 個のノード (メジアンノード) を選択した時に、各ノードの需要量とそのノードから最寄りのメジアンノードまでの距離の積の総和が小さくなるような $p$ 個のメジアンノードの組合せを求める組合せ最適化問題である。本稿では、この問題の拡張として、ネットワークの一部の構造のみを用いてメジアンノードを決定する問題を定式化する。現実のネットワークの多くは非常に大規模であり、その全体の構造を正確に把握することは容易ではない。そのため、ネットワークの一部の構造のみからメジアンノードを決定することができれば、最小 $p$-メジアン問題を現実の問題に応用する際に有用であると考えられる。本稿では、定式化した問題に対する発見的アルゴリズムを設計し、その有効性を実験的に評価する。その結果、ネットワーク全体の 10% 程度のノードの接続関係が入力として与えられれば、発見的アルゴリズムによって良好な解が求まることを示す。 |
(英) |
The minimum $p$-median problem is a combinatorial optimization problem finding a set of $p$ nodes in a network to minimize the weighted distance between each node and the nearest node in the median set. This paper formulates a generalization of the well known minimum $p$-median problem. Our problem aims to find the $p$-median set only from the incomplete information on the network. Studying this problem is motivated by the fact that it is difficult to accurately obtain the entire structure of real complex networks. This paper provides a simple heuristic algorithm for the minimum $p$-median problem for incomplete networks, and examines its effectiveness through experiments. Our results show that the formulated problem can be effectively solved by the heuristic algorithm even with a partial network constructed from a 10% node sampling. |
キーワード |
(和) |
最小$p$-メジアン問題 / ネットワークサンプリング / 組合せ最適化 / / / / / |
(英) |
minimum $p$-median problem / network sampling / combinatorial optimization / / / / / |
文献情報 |
信学技報, vol. 118, no. 395, CQ2018-85, pp. 53-58, 2019年1月. |
資料番号 |
CQ2018-85 |
発行日 |
2019-01-10 (CQ) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CQ2018-85 |
研究会情報 |
研究会 |
CQ CBE |
開催期間 |
2019-01-17 - 2019-01-18 |
開催地(和) |
首都大学東京 |
開催地(英) |
Tokyo Metropolitan Univ. |
テーマ(和) |
映像/音声サービスの品質、メディア品質、ネットワークの品質・QoS制御、災害時のネットワークとコミュニケーション、ユーザ行動、機械学習、一般 |
テーマ(英) |
Video/Voice Services Quality, Media Quality, Network Quality and QoS Control, Networks and Communications at Disaster, User Behavior, Machine Learning, etc. |
講演論文情報の詳細 |
申込み研究会 |
CQ |
会議コード |
2019-01-CQ-CBE |
本文の言語 |
日本語 |
タイトル(和) |
不完全なネットワークにおける最小p-メジアン問題 |
サブタイトル(和) |
定式化と実験的評価 |
タイトル(英) |
Minimum p-Median Problem for Incomplete Networks |
サブタイトル(英) |
A Formulation and Experimental Evaluation |
キーワード(1)(和/英) |
最小$p$-メジアン問題 / minimum $p$-median problem |
キーワード(2)(和/英) |
ネットワークサンプリング / network sampling |
キーワード(3)(和/英) |
組合せ最適化 / combinatorial optimization |
キーワード(4)(和/英) |
/ |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
津川 翔 / Sho Tsugawa / ツガワ ショウ |
第1著者 所属(和/英) |
筑波大学 (略称: 筑波大)
University of Tsukuba (略称: Univ. of Tsukuba) |
第2著者 氏名(和/英/ヨミ) |
大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ |
第2著者 所属(和/英) |
関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2019-01-18 11:20:00 |
発表時間 |
25分 |
申込先研究会 |
CQ |
資料番号 |
CQ2018-85 |
巻番号(vol) |
vol.118 |
号番号(no) |
no.395 |
ページ範囲 |
pp.53-58 |
ページ数 |
6 |
発行日 |
2019-01-10 (CQ) |
|