文献

J-GLOBAL ID：202002245142965921   整理番号：20A1394795

2分散問題に対する近似アルゴリズム

An Approximation Algorithm for the 2-Dispersion Problem

著者 (2件)： AMANO Kazuyuki (Gunma University) ,  NAKANO Shin-ichi (Gunma University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E103.D  号： 3  ページ： 506-508(J-STAGE)  発行年： 2020年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Pを平面上の点の集合とし,d(p,q)をPにおける点p,qの対間の距離とする。点p∈Pおよび|S|≧3の部分集合S⊂P,Sに関するpの,コスト₂(p,S)で示す,2分散コストは,(1)S\{p}におけるpから最も近い点までの距離および(2)S\{p}におけるpから2番目に最も近い点までの距離の合計である。|S|≧3のS⊂Pの2分散コストcost₂(S)は,min_p∈Δ{cost₂(p,S)}である。n点の集合Pと整数kを与えられた場合,筆者らは最大cost₂(S)でPのk点部分集合Sを計算する。本論文で筆者らは,この問題に対する簡単な1/(4√3)近似アルゴリズムを与えた。(翻訳著者抄録)

シソーラス用語： *分散【dispersion】 ,  *近似法 ,  *集合 ,  点 ,  部分集合 ,  距離 ,  整数 ,  *近似アルゴリズム

著者キーワード (2件)： 分散問題 ,  近似アルゴリズム

分類 (2件)： 数値計算  (JE02000J) ,  数値解析,近似法  (AB04000F)

引用文献 (12件)：

• [1] K. Amano and S. Nakano, Away from Rivals, 30th Canadian Conference on Computational Geometry, Session 2B, University of Manitoba, Aug. 8-10, 2018.
• [2] C. Baur and S.P. Fekete, “Approximation of Geometric Dispersion Problems,” Proc. of APPROX '98, pp.63-75, 1998. 10.1007/bfb0053964
• [3] A. Cevallos, F. Eisenbrand, and R. Zenklusen, “Local search for max-sum diversification,” Proc. of SODA '17, pp.130-142, 2017. 10.1137/1.9781611974782.9
• [4] B. Chandra and M.M. Halldórsson, “Approximation Algorithms for Dispersion Problems,” J. of Algorithms, vol.38, no.2, pp.438-465, 2001. 10.1006/jagm.2000.1145
• [5] Z. Drezner, Facility Location: A Survey of Applications and Methods, Springer, 1995.

タイトルに関連する用語 (1件)： 近似アルゴリズム