文献

J-GLOBAL ID：202202258238220698   整理番号：22A1157842

固定次元における幾何学的中心ベース問題の線形サイズ普遍離散化【JST・京大機械翻訳】

Linear-size universal discretization of geometric center-based problems in fixed dimensions

著者 (1件)： Shenmaier Vladimir (Sobolev Institute of Mathematics, Novosibirsk, Russia)
資料名： Journal of Combinatorial Optimization  (Journal of Combinatorial Optimization)
巻： 43  号： 3  ページ： 528-542  発行年： 2022年 
JST資料番号： W1143A  ISSN： 1382-6905  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 多くの幾何学的最適化問題は,中心から与えられた入力点までの距離に連続的に依存する目的関数を最小化する空間(中心)の点を見つけることができる。用例は,k-平均,幾何学的k-Median/Center,連続施設配置,m-Varianceなどである。任意の固定[数式:原文を参照]に対して,任意のベクトルノルムで誘起されたメトリックを有する固定次元空間におけるn入力点のあらゆるセットは,ほぼ線形時間で計算可能なO(n)候補中心の集合を許容し,全ての入力点までの距離に関して空間の各点の[数式:原文を参照]近似を含むことを証明した。それは,任意の連続性型目的関数を有する幾何学的中心ベース問題の普遍的近似保存低減を,中心がかなり小さい候補から選択されるそれらの離散バージョンに対して,与えた。候補のそのような線形サイズ集合の存在も固定倍加次元の任意の計量空間に対して示した。Copyright The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 最適化 ,  ベクトル ,  距離 ,  近似法 ,  クラスタ化 ,  空間 ,  線形性 ,  平均値 ,  目的関数 ,  連続性 ,  *次元 ,  ノルム
準シソーラス用語： *離散化 ,  ホップ数 ,  幾何学的最適化 , 【Automatic Indexing@JST】

著者キーワード (6件)： 幾何学的最適化 ,  クラスタリング ,  施設配置 ,  計量空間 ,  近似中心 ,  離散化

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  数値計算  (JE02000J)

タイトルに関連する用語 (6件)： 次元 ,  幾何学 ,  問題 ,  線形 ,  サイズ ,  離散化