論文の概要: Tight FPT Approximation for Constrained k-Center and k-Supplier
- arxiv url: http://arxiv.org/abs/2110.14242v1
- Date: Wed, 27 Oct 2021 07:52:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 15:07:38.176076
- Title: Tight FPT Approximation for Constrained k-Center and k-Supplier
- Title（参考訳）: 拘束k-Centerとk-SupplierのタイトFPT近似
- Authors: Dishant Goyal and Ragesh Jaiswal
- Abstract要約: 我々は、$k$-supplierと$k$-center問題の制約付きバージョンについて検討する。
Ding と Xu [SODA 2015] は、$k$-median と $k$-means の目的という文脈で、制約付きクラスタリングのための統一されたフレームワークを提案した。
- 参考スコア（独自算出の注目度）: 0.38073142980733
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study a range of constrained versions of the $k$-supplier
and $k$-center problems such as: capacitated, fault-tolerant, fair, etc. These
problems fall under a broad framework of constrained clustering. A unified
framework for constrained clustering was proposed by Ding and Xu [SODA 2015] in
context of the $k$-median and $k$-means objectives. In this work, we extend
this framework to the $k$-supplier and $k$-center objectives. This unified
framework allows us to obtain results simultaneously for the following
constrained versions of the $k$-supplier problem: $r$-gather, $r$-capacity,
balanced, chromatic, fault-tolerant, strongly private, $\ell$-diversity, and
fair $k$-supplier problems, with and without outliers. We obtain the following
results: We give $3$ and $2$ approximation algorithms for the constrained
$k$-supplier and $k$-center problems, respectively, with $\mathsf{FPT}$ running
time $k^{O(k)} \cdot n^{O(1)}$, where $n = |C \cup L|$. Moreover, these
approximation guarantees are tight; that is, for any constant $\epsilon>0$, no
algorithm can achieve $(3-\epsilon)$ and $(2-\epsilon)$ approximation
guarantees for the constrained $k$-supplier and $k$-center problems in
$\mathsf{FPT}$ time, assuming $\mathsf{FPT} \neq \mathsf{W}[2]$. Furthermore,
we study these constrained problems in outlier setting. Our algorithm gives $3$
and $2$ approximation guarantees for the constrained outlier $k$-supplier and
$k$-center problems, respectively, with $\mathsf{FPT}$ running time
$(k+m)^{O(k)} \cdot n^{O(1)}$, where $n = |C \cup L|$ and $m$ is the number of
outliers.
- Abstract（参考訳）: 本研究では,容量化,フォールトトレラント,フェアなど,k$-supplierおよびk$-center問題の制約付きバージョンについて検討する。
これらの問題は、制約付きクラスタリングの幅広い枠組みに該当する。
Ding と Xu [SODA 2015] は、$k$-median と $k$-means の目的という文脈で、制約付きクラスタリングのための統一されたフレームワークを提案した。
この作業では、このフレームワークを$k$-supplierと$k$-centerの目的に拡張します。
この統合されたフレームワークは、以下の制約付きバージョンの$k$-supplier問題に対して、同時に結果を得ることができる:$r$-gather, $r$-capacity, balanced,chromeatic, fault-tolerant, strongly private, $\ell$-diversity, fair $k$-supplier problem, with with and without outliers。
制約付き$k$-supplier と $k$-center 問題に対して、それぞれ$$$$2$の近似アルゴリズムを与え、$\mathsf{FPT}$ run time $k^{O(k)} \cdot n^{O(1)}$, $n = |C \cup L|$とする。
さらに、これらの近似保証は厳密であり、すなわち任意の定数 $\epsilon>0$ に対して、任意のアルゴリズムが $(3-\epsilon)$ と $(2-\epsilon)$ を達成できない、すなわち、制約付き $k$-supplier と $k$-center の問題を $\mathsf{FPT}$ time で、$\mathsf{FPT} \neq \mathsf{W}[2]$
さらに,これらの制約付き問題を外乱設定で検討する。
我々のアルゴリズムは、制約付きアウトリーの$k$-supplierと$k$-center問題に対して、それぞれ3$と2$の近似保証を与え、$\mathsf{FPT}$ run time $(k+m)^{O(k)} \cdot n^{O(1)}$で、$n = |C \cup L|$と$m$はアウトリーの数値である。
関連論文リスト
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.697784653113095]
すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。
私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
論文 参考訳（メタデータ） (2024-05-16T18:17:44Z) - An Analysis of $D^\alpha$ seeding for $k$-means [11.394909061094461]
実際に$alpha>2$は、$D2$のシードに比べて$k$-meansのコストを改善することができる。
以上のパラメータが$Dalphaシードに与える影響を実験的に確認する。
論文 参考訳（メタデータ） (2023-10-20T13:15:18Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - 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) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。
我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文 参考訳（メタデータ） (2022-02-03T03:45:45Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。