論文の概要: Hardness of Approximation of Euclidean $k$-Median
- arxiv url: http://arxiv.org/abs/2011.04221v1
- Date: Mon, 9 Nov 2020 06:50:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 02:39:09.139189
- Title: Hardness of Approximation of Euclidean $k$-Median
- Title（参考訳）: ユークリッド$k$-Medianの近似の硬さ
- Authors: Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal
- Abstract要約: a set $mathcalX$ of $n$ points in $mathbbRd$, find a set $C subset mathbbRd$ of $k$ points(センターと呼ばれる)。
本研究では、ユークリッドの$k$-median問題に対する近似結果の最初の難しさについて述べる。
- 参考スコア（独自算出の注目度）: 0.25782420501870296
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Euclidean $k$-median problem is defined in the following manner: given a
set $\mathcal{X}$ of $n$ points in $\mathbb{R}^{d}$, and an integer $k$, find a
set $C \subset \mathbb{R}^{d}$ of $k$ points (called centers) such that the
cost function $\Phi(C,\mathcal{X}) \equiv \sum_{x \in \mathcal{X}} \min_{c \in
C} \|x-c\|_{2}$ is minimized. The Euclidean $k$-means problem is defined
similarly by replacing the distance with squared distance in the cost function.
Various hardness of approximation results are known for the Euclidean $k$-means
problem. However, no hardness of approximation results were known for the
Euclidean $k$-median problem. In this work, assuming the unique games
conjecture (UGC), we provide the first hardness of approximation result for the
Euclidean $k$-median problem.
Furthermore, we study the hardness of approximation for the Euclidean
$k$-means/$k$-median problems in the bi-criteria setting where an algorithm is
allowed to choose more than $k$ centers. That is, bi-criteria approximation
algorithms are allowed to output $\beta k$ centers (for constant $\beta>1$) and
the approximation ratio is computed with respect to the optimal
$k$-means/$k$-median cost. In this setting, we show the first hardness of
approximation result for the Euclidean $k$-median problem for any $\beta <
1.015$, assuming UGC. We also show a similar bi-criteria hardness of
approximation result for the Euclidean $k$-means problem with a stronger bound
of $\beta < 1.28$, again assuming UGC.
- Abstract（参考訳）: ユークリッドの$k$-median問題は次の方法で定義される: $\mathcal{x}$ of $n$ points in $\mathbb{r}^{d}$, and an integer $k$, if a set $c \subset \mathbb{r}^{d}$ of $k$ points (いわゆるセンター) であり、コスト関数 $\phi(c,\mathcal{x}) \equiv \sum_{x \in \mathcal{x}} \min_{c \in c} \|x-c\|_{2}$ は最小である。
ユークリッド$k$-平均問題は、コスト関数において距離を2乗距離に置き換えることで同様に定義される。
近似結果の様々な困難さはユークリッドの$k$-means問題で知られている。
しかし、近似結果の難しさはユークリッドの$k$-median問題では知られていなかった。
この研究において、一意ゲーム予想 (UGC) を仮定すると、ユークリッド$k$-中間問題に対して近似結果の最初の硬度を与える。
さらに、アルゴリズムが$k$中心以上を選択できるbi-criteria設定におけるユークリッド問題である$k$-means/$k$-median問題の近似の難しさについて検討する。
すなわち、bi-criteria approximationアルゴリズムは、$\beta k$center(定数$\beta>1$)を出力することができ、最適な$k$-means/$k$-medianコストに対して近似比を算出する。
この設定では、UGCを仮定して任意の$\beta <1.015$に対してユークリッド$k$-median問題に対する近似結果の最初の困難さを示す。
また、ugc を仮定して、より強い値が $\beta < 1.28$ であるユークリッド問題に対する近似結果の類似の双ユークリッド硬さを示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - 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) - Bicriteria Approximation Algorithms for Priority Matroid Median [1.7188280334580193]
我々は、プライオリティを$k$-Median問題に一般化する、プライオリティ・マトロイド・メディア問題を考える。
目標は、mathcalF ff_iの$sum_iを最小化するために、サブセット$S subseteq MathcalF$を選択することである。
論文 参考訳（メタデータ） (2022-10-04T20:19:55Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain [11.562923882714093]
Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。
我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
論文 参考訳（メタデータ） (2021-10-08T07:46:18Z) - FPT Approximation for Socially Fair Clustering [0.38073142980733]
距離関数 $d(.,.)$ を持つ距離空間 $mathcalX$ において点の集合 $P$ が与えられる。
社会的に公正な$k$-median問題の目標は、すべてのグループに対する最大平均コストを最小限に抑える、セットの$CサブセットF$ of $k$センターを見つけることである。
本研究では、社会的に公正な$k$-medianと$k$-meansに対する$(5+varepsilon)$と$(33+varepsilon)$近似アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-12T11:53:18Z) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。
局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文 参考訳（メタデータ） (2021-05-31T14:41:40Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。