論文の概要: Coreset-based Strategies for Robust Center-type Problems
- arxiv url: http://arxiv.org/abs/2002.07463v1
- Date: Tue, 18 Feb 2020 10:04:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 20:54:06.977758
- Title: Coreset-based Strategies for Robust Center-type Problems
- Title（参考訳）: ロバスト中心型問題に対するコアセットに基づく戦略
- Authors: Andrea Pietracaprina, Geppino Pucci, Federico Sold\`a
- Abstract要約: 我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。
パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 0.6875312133832077
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a dataset $V$ of points from some metric space, the popular $k$-center
problem requires to identify a subset of $k$ points (centers) in $V$ minimizing
the maximum distance of any point of $V$ from its closest center. The
\emph{robust} formulation of the problem features a further parameter $z$ and
allows up to $z$ points of $V$ (outliers) to be disregarded when computing the
maximum distance from the centers. In this paper, we focus on two important
constrained variants of the robust $k$-center problem, namely, the Robust
Matroid Center (RMC) problem, where the set of returned centers are constrained
to be an independent set of a matroid of rank $k$ built on $V$, and the Robust
Knapsack Center (RKC) problem, where each element $i\in V$ is given a positive
weight $w_i<1$ and the aggregate weight of the returned centers must be at most
1. We devise coreset-based strategies for the two problems which yield
efficient sequential, MapReduce, and Streaming algorithms. More specifically,
for any fixed $\epsilon>0$, the algorithms return solutions featuring a
$(3+\epsilon)$-approximation ratio, which is a mere additive term $\epsilon$
away from the 3-approximations achievable by the best known polynomial-time
sequential algorithms for the two problems. Moreover, the algorithms
obliviously adapt to the intrinsic complexity of the dataset, captured by its
doubling dimension $D$. For wide ranges of the parameters $k,z,\epsilon, D$, we
obtain a sequential algorithm with running time linear in $|V|$, and
MapReduce/Streaming algorithms with few rounds/passes and substantially
sublinear local/working memory.
- Abstract（参考訳）: ある距離空間からの点のデータセット$V$を与えられた場合、一般的な$k$-center問題は、その最も近い中心からの任意の点の最大距離を最小化するために$k$ポイント(中心)のサブセットを特定する必要がある。
問題の定式化である \emph{robust} は、さらにパラメータである$z$ を特徴とし、中心からの距離を計算した場合に最大$v$ (outliers) の$z$ポイントを無視できる。
本稿では,ロバストな $k$-center 問題の2つの重要な制約付き変種,すなわちロバスト・マトロイド・センター (rmc) 問題,すなわち,返却された中心の集合が $v$ に基づいて構築されたランク $k$ のマトロイドの独立集合として制約されるようなロバスト・マトロイド・センター (rmc) 問題,および各要素 $i\in v$ が正のウェイト $w_i<1$ と返却された中心の合計重量が 1 以上でなければならないロバスト・ナップサック・センター (rkc) 問題に焦点を当てた。
効率的なシーケンシャル,mapreduce,ストリーミングアルゴリズムを実現する2つの問題に対して,coresetベースの戦略を考案する。
より具体的には、固定された$\epsilon>0$ に対して、アルゴリズムは、(3+\epsilon)$-approximation ratio を特徴とする解を返す。
さらに、アルゴリズムはデータセットの本質的な複雑さに明らかに適応し、その倍の次元$D$でキャプチャされる。
パラメータ $k,z,\epsilon, D$ の幅広い範囲に対して,$|V|$ のランニング時間線形な逐次アルゴリズムと,ラウンド/パスが少ないMapReduce/ストリーミングアルゴリズムと,実質的にサブ線形な局所/ワーキングメモリを得る。
関連論文リスト
- Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
$ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。
我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。
我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
論文 参考訳（メタデータ） (2024-07-03T16:49:28Z) - 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Dynamic algorithms for k-center on graphs [3.568439282784197]
エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。
完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
論文 参考訳（メタデータ） (2023-07-28T13:50:57Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Revisiting Priority $k$-Center: Fairness and Outliers [5.3898004059026325]
我々は,プライオリティ $k$-center に対して定数係数近似アルゴリズムを導出するフレームワークを開発した。
私たちのフレームワークは,matroid と knapsack の制約に対する優先度 $k$-center の一般化にも拡張しています。
論文 参考訳（メタデータ） (2021-03-04T21:15:37Z) - No-Substitution $k$-means Clustering with Low Center Complexity and
Memory [5.837881923712394]
中心複雑性を$Lower_36, k(X)$で有界なアルゴリズムを開発し、これは真の$O(1)$-近似であり、近似係数は$k$または$n$とは独立である。
このアルゴリズムは、$Lower_36, k(X)$で区切られた最初の既知のアルゴリズムであり、これは真の$O(1)$-近似であり、近似係数は$k$または$n$から独立している。
論文 参考訳（メタデータ） (2021-02-18T01:20:03Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。