グラフにおける1メジアン問題の効率的近似アルゴリズム

TABATA Koji; NAKAMURA Atsuyoshi; KUDO Mineichi

文献

J-GLOBAL ID：201702278966841913 整理番号：17A0777169

グラフにおける1メジアン問題の効率的近似アルゴリズム

An Efficient Approximate Algorithm for the 1-Median Problem on a Graph

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=17A0777169&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=17A0777169&from=J-GLOBAL&jstjournalNo=U0469A") }}

著者 (3件)： , ,
資料名：
巻： E100.D 号： 5 ページ： 994-1002(J-STAGE) 発行年： 2017年
JST資料番号： U0469A ISSN： 1745-1361 資料種別：逐次刊行物 (A)
記事区分：短報発行国：日本 (JPN) 言語：英語 (EN)

著者らは,1メジアン問題に対する発見的近似アルゴリズムを提案した。1メジアン問題は,最も近い近似性を有する頂点を見つける問題であった。提案のアルゴリズムは,ランダムに選択した頂点から開始して,より簡単なスパニングサブグラフを使用した。そして,各頂点の近接中心性を近似的に計算することによって,より高い近接中心性を持つ頂点を見つけることを繰り返したが,ショートカットを持つk-近傍の密な最短経路グラフとそれを呼んだ。頂点数が10,000を超える実際のネットワークを使用した実験結果によれば,提案のアルゴリズムは,網羅的なサーチよりも100倍以上高速であり,頂点への注釈付き情報を用いる最先端の近似アルゴリズムよりも20倍以上高速であるが,提案のアルゴリズムによる解の出力は,より高い近似比を有した。(翻訳著者抄録)

, , , , , , , , ,
, ,

著者キーワード (3件)： , ,

計算理論 , グラフ理論基礎

引用文献 (15件)：

[1] O. Alp, E. Erkut, and Z. Drezner, “An efficient genetic algorithm for the p-median problem,” Annals of Operations research, vol.122(1-4), pp.21-42, 2003.
[2] R.E. Burkard and J. Krarup, “A linear algorithm for the pos/neg-weighted 1-median problem on a cactus,” Computing, vol.60, no.3, pp.193-215, 1998.
[3] M.L. Fredman and R.E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” J. ACM (JACM), vol.34, no.3, pp.596-615, 1987.
[4] L.C. Freeman, “Centrality in social networks conceptual clarification,” Social networks, vol.1, no.3, pp.215-239, 1978.
[5] A.J. Goldman, “Optimal center location in simple networks,” Transportation science, vol.5, no.2, pp.212-221, 1971.

, , ,

前のページに戻る