論文の概要: Bicriteria Approximation Algorithms for Priority Matroid Median
- arxiv url: http://arxiv.org/abs/2210.01888v2
- Date: Thu, 6 Jul 2023 18:36:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-10 16:05:02.178276
- Title: Bicriteria Approximation Algorithms for Priority Matroid Median
- Title（参考訳）: 優先マトロイド中央値に対するbicriteria近似アルゴリズム
- Authors: Tanvi Bajpai and Chandra Chekuri
- Abstract要約: 我々は、プライオリティを$k$-Median問題に一般化する、プライオリティ・マトロイド・メディア問題を考える。
目標は、mathcalF ff_iの$sum_iを最小化するために、サブセット$S subseteq MathcalF$を選択することである。
- 参考スコア（独自算出の注目度）: 1.7188280334580193
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Fairness considerations have motivated new clustering problems and algorithms
in recent years. In this paper we consider the Priority Matroid Median problem
which generalizes the Priority $k$-Median problem that has recently been
studied. The input consists of a set of facilities $\mathcal{F}$ and a set of
clients $\mathcal{C}$ that lie in a metric space $(\mathcal{F} \cup
\mathcal{C},d)$, and a matroid $\mathcal{M}=(\mathcal{F},\mathcal{I})$ over the
facilities. In addition each client $j$ has a specified radius $r_j \ge 0$ and
each facility $i \in \mathcal{F}$ has an opening cost $f_i$. The goal is to
choose a subset $S \subseteq \mathcal{F}$ of facilities to minimize the
$\sum_{i \in \mathcal{F}} f_i + \sum_{j \in \mathcal{C}} d(j,S)$ subject to two
constraints: (i) $S$ is an independent set in $\mathcal{M}$ (that is $S \in
\mathcal{I}$) and (ii) for each client $j$, its distance to an open facility is
at most $r_j$ (that is, $d(j,S) \le r_j$). For this problem we describe the
first bicriteria $(c_1,c_2)$ approximations for fixed constants $c_1,c_2$: the
radius constraints of the clients are violated by at most a factor of $c_1$ and
the objective cost is at most $c_2$ times the optimum cost. We also improve the
previously known bicriteria approximation for the uniform radius setting ($r_j
:= L$ $\forall j \in \mathcal{C}$).
- Abstract（参考訳）: フェアネスの考慮は近年、新しいクラスタリング問題とアルゴリズムを動機付けている。
本稿では,最近研究されている優先度 $k$-median 問題を一般化した優先度マトロイド中央値問題を考える。
入力は、一連の施設$\mathcal{F}$と、計量空間$(\mathcal{F} \cup \mathcal{C},d)$にあるクライアント$\mathcal{C}$と、その施設上のマトロイド$\mathcal{M}=(\mathcal{F},\mathcal{I})$からなる。
さらに、各クライアント$j$ は特定の半径 $r_j \ge 0$ を持ち、各施設 $i \in \mathcal{F}$ は開封コスト $f_i$ を持つ。
目的は、$\sum_{i \in \mathcal{F}} f_i + \sum_{j \in \mathcal{C}} d(j,S)$ を最小化する施設のサブセット $S \subseteq \mathcal{F}$ を選択することである。
(i)$S$は$\mathcal{M}$の独立集合である(つまり$S \in \mathcal{I}$)。
(ii) 各クライアント$j$に対して、開施設までの距離は最大$r_j$(つまり$d(j,S) \le r_j$)である。
この問題に対して、最初のbicriteria $(c_1,c_2)$の固定定数に対する近似を記述する: クライアントの半径制約は、少なくとも$c_1$の係数で破られ、目的コストは最適なコストの最大$c_2$倍である。
また、一様半径設定(r_j := L$ $\forall j \in \mathcal{C}$)に対する既知双基準近似も改善する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - 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) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - 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) - Hardness of Approximation of Euclidean $k$-Median [0.25782420501870296]
a set $mathcalX$ of $n$ points in $mathbbRd$, find a set $C subset mathbbRd$ of $k$ points(センターと呼ばれる)。
本研究では、ユークリッドの$k$-median問題に対する近似結果の最初の難しさについて述べる。
論文 参考訳（メタデータ） (2020-11-09T06:50:34Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳（メタデータ） (2020-03-09T13:30:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。