入れ子型準独立集合によるEuclidk-meansとk-メディアンに対する改良された近似【JST・京大機械翻訳】

Cohen-Addad Vincent; Esfandiari Hossein; Mirrokni Vahab; Narayanan Shyam

プレプリント

J-GLOBAL ID：202202216378391919 整理番号：22P0329250

入れ子型準独立集合によるEuclidk-meansとk-メディアンに対する改良された近似【JST・京大機械翻訳】

Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年04月10日プレプリントサーバーでの情報更新日： 2022年04月11日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

データ解析と機械学習アプリケーションによって動機づけられて,一般的な高次元ユークリッドk-中央値とk-平均問題を考察した。著者らは,JainとVazianiの古典的アルゴリズムおよびAhmadian,Noouzi-Fard,Svensson,およびWardの最近アルゴリズムによって触発された,新しいプライマー二重アルゴリズムを提案した。本アルゴリズムは,ユークリッドk-中央値とk-平均に対して,それぞれ2.406と5.912の近似比を達成し,Ahmadianらの2.633近似比と,Grandoni,Ostrovsky,Rabani,Schulman,およびVenkatの6.1291近似比を改善した。この技法はユークリッドクラスタリングに関する以前の研究よりもユークリッドメトリックのはるかに強い利用を含む。さらに,筆者らは”ネスト化準独立集合”をdubするグラフ上の独立集合のバリアントを用いて過剰中心を除去する新しい方法を導入した。次に,この技術はユークリッドとl_pメトリック空間における他の最適化問題にとって興味深い。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , 【Automatic Indexing@JST】

計算理論 , 数値計算

, ,

前のページに戻る