論文の概要: Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means
- arxiv url: http://arxiv.org/abs/2611.14892v1
- Date: Wed, 11 Nov 2026 01:28:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 11:08:29.299108
- Title: Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means
- Title(参考訳): ユークリッドk平均近似のためのほぼETH下のほぼ最適下界
- Abstract要約: ユークリッドの$k$-平均問題では、$mathbbRd$で$n$の点の集合が与えられる。
目的は、各点から最も近い代表への平方距離の和を最小化するために、空間内の代表点を$k$で見つけることである。
at all constant $in(0,1)$, Euclidean $k$-means in $mathbbRd$ has no $(1+varepsilon)$-approximation algorithm running in time $2(k/varepsilon)
- 参考スコア(独自算出の注目度): 3.6381860041528085
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the Euclidean $k$-means problem, we are given a set of $n$ points in $\mathbb{R}^d$, and the goal is to find $k$ representative points in space so as to minimize the sum of the squared distances from each point to its closest representative. Algorithmically, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] obtain a $(1+\varepsilon)$-approximation for high-dimensional Euclidean $k$-means in time $2^{(k/\varepsilon)^{O(1)}} \cdot dn^{O(1)}$, which was subsequently improved to $2^{\tilde{O}(k/\varepsilon)} + O(ndk)$ by Feldman, Monemizadeh, and Sohler [SoCG'07]. On the lower-bound side, a recent work of Cohen-Addad, Karthik, Saulpic, and Schwiegelshohn [SoCG'26] proposed the Exponential Time for Expanders Hypothesis (XXH), which asserts exponential-time hardness for $(1+\varepsilon)$-approximating Vertex Cover on vertex expanders, and used it to prove nearly matching running time lower bound whenever $k=\tildeω(1/\varepsilon)$. We observe that XXH does not hold in the parameter regime needed for the above result, and show how to repair their reduction under a more standard assumption. More precisely, we show that assuming the Almost Exponential Time Hypothesis for 3-SAT (Almost ETH), for every constant $β\in(0,1)$, Euclidean $k$-means in $\mathbb{R}^d$ has no $(1+\varepsilon)$-approximation algorithm running in time $2^{(k/\varepsilon)^{1-β}}\text{poly}(n,d)$, whenever $k=\tildeω(1/\varepsilon)$. By modifying the construction, we also obtain a similar result for approximating the Euclidean $k$-median problem.
- Abstract(参考訳): ユークリッドの$k$-平均問題では、$\mathbb{R}^d$で$n$の点の集合が与えられ、その目標は、各点から最も近い代表への平方距離の和を最小化するために、空間上の$k$の代表点を見つけることである。
de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] obtained a $(1+\varepsilon)$-approximation for high-dimensional Euclidean $k$-means in time $2^{(k/\varepsilon)^{O(1)}} \cdot dn^{O(1)}$, then improved to $2^{\tilde{O}(k/\varepsilon)} + O(ndk)$ by Feldman, Monemizadeh, and Sohler [SoCG'07]
ローバウンド側では、Cohen-Addad, Karthik, Saulpic, Schwiegelshohn [SoCG'26] の最近の研究は、指数時間硬度が$(1+\varepsilon)$-approximating Vertex Cover on vertex expander と主張するExpanders hypothesis (XXH) を提案した。
XXHは上記の結果に必要なパラメータ体系を保たず、より標準的な仮定の下でその縮小を修復する方法を示す。
より正確には、すべての定数 $β\in(0,1)$, Euclidean $k$-means in $\mathbb{R}^d$ has no $(1+\varepsilon)$-approximation algorithm running in time $2^{(k/\varepsilon)^{1-β}}\text{poly}(n,d)$, when $k=\tildeω(1/\varepsilon)$.} に対して 3-SAT (Almost ETH) のほぼ指数時間仮説を仮定する。
構成を変更することで、ユークリッドの$k$-median問題を近似する同様の結果が得られる。
関連論文リスト
- Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL [63.08320557041278]
本稿では,Chamfer 距離を $ell_p ノルムで 1 p le 2$ で近似する効率的なアルゴリズムを提案する。
チャムファー距離を保存するのに十分であることを示す。
また, ストリーミング環境における角距離および上下境界について, 追加的な結果を与える。
論文 参考訳(メタデータ) (2026-11-08T05:46:25Z) - Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model [37.35522173770848]
対称ポリトープ$P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$のジョン・エリプシドは、長いレバレッジスコアアルゴリズムによって計算される。
論文 参考訳(メタデータ) (2026-06-18T11:00:03Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳(メタデータ) (2025-09-20T20:18:49Z) - Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。
分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文 参考訳(メタデータ) (2025-04-29T15:56:48Z) - Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳(メタデータ) (2024-06-04T15:50:42Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Improved Coresets for Euclidean $k$-Means [24.850829728643923]
1組の$d$次元の$n$ポイントが与えられたとき、ユークリッド$k$平均問題(ユークリッド$k$中間問題を参照)は、$k$センターを見つけることからなる。
本稿では,$tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon)を改善する。
論文 参考訳(メタデータ) (2022-11-15T14:47:24Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳(メタデータ) (2021-06-25T19:14:45Z) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳(メタデータ) (2020-06-23T20:21:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。