電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2019-01-18 11:20
不完全なネットワークにおける最小p-メジアン問題 ~ 定式化と実験的評価 ~
津川 翔筑波大)・大崎博之関西学院大
技報オンラインサービス実施中
抄録 (和) 最小 $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 Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2019-01-18 11:20:00 
発表時間 25 
申込先研究会 CQ 
資料番号 IEICE-CQ2018-85 
巻番号(vol) IEICE-118 
号番号(no) no.395 
ページ範囲 pp.53-58 
ページ数 IEICE-6 
発行日 IEICE-CQ-2019-01-10 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会