お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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 
ページ数
発行日 2019-01-10 (CQ) 


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

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


IEICE / 電子情報通信学会