文献

J-GLOBAL ID：202202245089821817   整理番号：22A0729485

ユークリッドk平均に対する洗練された近似【JST・京大機械翻訳】

A refined approximation for Euclidean k-means

著者 (5件)： Grandoni Fabrizio (IDSIA, USI-SUPSI, Switzerland) ,  Ostrovsky Rafail (UCLA, United States of America) ,  Rabani Yuval (The Hebrew University of Jerusalem, Israel) ,  Schulman Leonard J. (Caltech, United States of America) ,  Venkat Rakesh (IIT Hyderabad, India)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 176  ページ： Null  発行年： 2022年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Euclid k-Means問題において,ユークリッド空間と正の整数kにおけるn点Dの収集を与えた。著者らの目標は,Dと最も近い中心における各点間の二乗ユークリッド距離の合計を最小化するように,同じ空間(中心)におけるk点の収集を同定することである。この問題はAPX困難であり,現在の最良近似比は問題に対する標準LP(Ahmadian et al.FOCS’17,SICOMP’20)に基づく一次-二重6.357近似である。このノートでは,Ahmadianらの解析の僅かな修正が,わずかに改善された6.12903近似をもたらすことを示す。関連する結果として,言及したLPは少なくとも16+515>1.2157の積分ギャップを持つことを示した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *近似法 ,  Euclid空間 ,  問題 ,  整数
準シソーラス用語： 近似アルゴリズム ,  Euclid距離 , 【Automatic Indexing@JST】

著者キーワード (4件)： 近似アルゴリズム ,  Euclidk平均 ,  ユークリッド施設配置 ,  完全性ギャップ

分類 (3件)： 数理計画法  (KA03030M) ,  分子の電子構造  (BH05010Q) ,  数値計算  (JE02000J)

タイトルに関連する用語 (2件)： 平均 ,  近似