論文の概要: Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces

• arxiv url: http://arxiv.org/abs/2305.07316v2
• Date: Mon, 16 Sep 2024 14:13:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-18 03:58:31.674819
• Title: Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
• Title（参考訳）: 離散幾何学空間におけるロバストクラスタリングのパラメータ近似
• Authors: Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase,
• Abstract要約: 次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
• 参考スコア（独自算出の注目度）: 2.687607197645453
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the well-studied Robust $(k, z)$-Clustering problem, which generalizes the classic $k$-Median, $k$-Means, and $k$-Center problems. Given a constant $z\ge 1$, the input to Robust $(k, z)$-Clustering is a set $P$ of $n$ weighted points in a metric space $(M,\delta)$ and a positive integer $k$. Further, each point belongs to one (or more) of the $m$ many different groups $S_1,S_2,\ldots,S_m$. Our goal is to find a set $X$ of $k$ centers such that $\max_{i \in [m]} \sum_{p \in S_i} w(p) \delta(p,X)^z$ is minimized. This problem arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For polynomial time computation, an approximation factor of $O(\log m/\log\log m)$ is known [Makarychev, Vakilian, COLT $2021$], which is tight under a plausible complexity assumption even in the line metrics. For FPT time, there is a $(3^z+\epsilon)$-approximation algorithm, which is tight under GAP-ETH [Goyal, Jaiswal, Inf. Proc. Letters, 2023]. Motivated by the tight lower bounds for general discrete metrics, we focus on \emph{geometric} spaces such as the (discrete) high-dimensional Euclidean setting and metrics of low doubling dimension, which play an important role in data analysis applications. First, for a universal constant $\eta_0 >0.0006$, we devise a $3^z(1-\eta_{0})$-factor FPT approximation algorithm for discrete high-dimensional Euclidean spaces thereby bypassing the lower bound for general metrics. We complement this result by showing that even the special case of $k$-Center in dimension $\Theta(\log n)$ is $(\sqrt{3/2}- o(1))$-hard to approximate for FPT algorithms. Finally, we complete the FPT approximation landscape by designing an FPT $(1+\epsilon)$-approximation scheme (EPAS) for the metric of sub-logarithmic doubling dimension.
• Abstract（参考訳）: 我々は、古典的な$k$-Median, $k$-Means, $k$-Center問題を一般化する、よく研究されたRobust $(k, z)$-Clustering問題を考える。 定数 $z\ge 1$ が与えられたとき、Robust $(k, z)$-Clustering への入力は、計量空間 $(M,\delta)$ における集合 $P$ of $n$ 重み付き点と正の整数 $k$ である。 さらに、各点は、多くの異なる群$S_1,S_2,\ldots,S_m$の1つ(またはそれ以上)に属する。 我々のゴールは、$\max_{i \in [m]} \sum_{p \in S_i} w(p) \delta(p,X)^z$ が最小となるような、$k$ の集合 $X$ を見つけることである。 この問題はロバスト最適化の領域(Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010)とアルゴリズムフェアネスの領域で発生する。 多項式時間計算の場合、$O(\log m/\log\log)の近似係数 m)$は[Makarychev, Vakilian, COLT 2021$]として知られています。 FPT時間には$(3^z+\epsilon)$-approximationアルゴリズムがあり、GAP-ETH(Goyal, Jaiswal, Inf. Proc. Letters, 2023)の下で厳密である。 一般的な離散的測度に対する厳密な下界によって動機付けられ、(離散的な)高次元ユークリッドの設定や低倍次元の測度など、データ解析の応用において重要な役割を担っている。 まず、普遍定数 $\eta_0 >0.0006$ に対して、離散高次元ユークリッド空間に対する3^z(1-\eta_{0})$-factor FPT近似アルゴリズムを考案し、一般計量に対する下界をバイパスする。 この結果は、次元 $\Theta(\log) の $k$-Center の特別な場合でさえも、この結果を補完する。 n)$ is $(\sqrt{3/2}-o(1))$-hard to almost for FPT algorithm。 最後に, FPT $(1+\epsilon)$-approximation scheme (EPAS) を設計することにより, FPT近似環境を完成させる。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
  勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。 規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
  論文  参考訳（メタデータ） (2023-06-16T17:00:51Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Sets Clustering [25.358415142404752]
  我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。 このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。 オープンソースコードと文書分類および施設位置の実験結果も提供される。
  論文  参考訳（メタデータ） (2020-03-09T13:30:30Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。