文献

J-GLOBAL ID：201002220570432063   整理番号：10A0307069

任意次元のクラスタリング問題のための線形時間近似スキーム

Linear-Time Approximation Schemes for Clustering Problems in Any Dimensions

著者 (3件)： KUMAR Amit (Indian Inst. Technol., New Delhi, IND) ,  SABHARWAL Yogish (IBM Res.-India, New Delhi, IND) ,  SEN Sandeep (Indian Inst. Technol., New Delhi, IND)
資料名： Journal of the ACM (Association for Computing Machinery)  (Journal of the ACM (Association for Computing Machinery))
巻： 57  号： 2  ページ： 5:1-5:32  発行年： 2010年01月 
JST資料番号： C0267A  ISSN： 0004-5411  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 任意次元の幾何的クラスタリング問題のための近似アルゴリズムを設計するための一般的アプローチを示した。具体的には,k-平均,k-メジアン,および離散k-平均問題向けのランダム化アルゴリズムを与えた。これらのアルゴリズムは線形時間で確率≧1/2の(1+ε)近似を算出する。そして,kおよびεを固定したn次元/dポイントの幾何的クラスタリング問題に関する最初の線形時間アルゴリズムである。また,ここで示したアプローチは一般的であり,単純な性質を満たすクラスタリング問題にも適用可能である。

シソーラス用語： アルゴリズム ,  *クラスタ化 ,  近似法 ,  計算量 ,  *計算機アルゴリズム ,  無作為抽出 ,  中央値 ,  平均値 ,  NP困難 ,  確率 ,  距離
準シソーラス用語： クラスタリングアルゴリズム ,  クラスタリング ,  近似アルゴリズム ,  ランダムサンプリング ,  メジアン ,  平均 ,  Euclid距離

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (6件)： 次元 ,  クラスタリング ,  問題 ,  線形 ,  近似 ,  スキーム