論文の概要: Covering a Few Submodular Constraints and Applications

• arxiv url: http://arxiv.org/abs/2507.09879v1
• Date: Mon, 14 Jul 2025 03:32:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:24.183635
• Title: Covering a Few Submodular Constraints and Applications
• Title（参考訳）: 部分モジュラ制約のカバーと応用
• Authors: Tanvi Bajpai, Chandra Chekuri, Pooja Kulkarni,
• Abstract要約: 複数の部分モジュラー制約を網羅する問題を考察する。 任意の整数に対して$alpha ge 1$ が集合 $S$ を出力し、$f_i(S) ge$ 1-1/ealpha -epsilon)b_i$ が [r]$ と $mathbbE[c(S)] le (1+epsilon)alpha cdot sfOPT$ に対して$1-1/ealpha -epsilon)b_i$ が成り立つ。
• 参考スコア（独自算出の注目度）: 1.649938899766112
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of covering multiple submodular constraints. Given a finite ground set $N$, a cost function $c: N \rightarrow \mathbb{R}_+$, $r$ monotone submodular functions $f_1,f_2,\ldots,f_r$ over $N$ and requirements $b_1,b_2,\ldots,b_r$ the goal is to find a minimum cost subset $S \subseteq N$ such that $f_i(S) \ge b_i$ for $1 \le i \le r$. When $r=1$ this is the well-known Submodular Set Cover problem. Previous work \cite{chekuri2022covering} considered the setting when $r$ is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each $f_i$ is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least $\Omega(\log r)$ which is unavoidable when $r$ is part of the input. In this paper, motivated by some recent applications, we consider the problem when $r$ is a \emph{fixed constant} and obtain two main results. For covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer $\alpha \ge 1$ outputs a set $S$ such that $f_i(S) \ge$ $(1-1/e^\alpha -\epsilon)b_i$ for each $i \in [r]$ and $\mathbb{E}[c(S)] \le (1+\epsilon)\alpha \cdot \sf{OPT}$. Second, when the $f_i$ are weighted coverage functions from a deletion-closed set system we obtain a $(1+\epsilon)$ $(\frac{e}{e-1})$ $(1+\beta)$-approximation where $\beta$ is the approximation ratio for the underlying set cover instances via the natural LP. These results show that one can obtain nearly as good an approximation for any fixed $r$ as what one would achieve for $r=1$. We mention some applications that follow easily from these general results and anticipate more in the future.
• Abstract（参考訳）: 複数の部分モジュラー制約を網羅する問題を考察する。 有限基底集合 $N$, a cost function $c: N \rightarrow \mathbb{R}_+$, $r$ monotone submodular function $f_1,f_2,\ldots,f_r$ over $N$ and requirements $b_1,b_2,\ldots,b_r$ この目標は、$f_i(S) \ge b_i$ for $1 \le i \le r$ の最小コスト部分集合 $S \subseteq N$ を見つけることである。 r=1$のとき、これはよく知られた部分モジュラ集合被覆問題である。 以前の研究 \cite{chekuri2022covering} では、$r$が大きければ設定を考慮し、bi-criteria approximationアルゴリズムを開発し、各$f_i$が重み付きカバレッジ関数である場合には、重要な特別なケースに対する近似アルゴリズムを開発した。 これらはかなり一般的なモデルであり、特殊ケースとしていくつかの具体的で興味深い問題を捉えている。 これらの問題の近似比は少なくとも$\Omega(\log r)$であり、$r$が入力の一部であれば避けられない。 本稿では、最近の応用によって動機づけられた問題として、$r$ が \emph{fixed constant} であり、2つの主要な結果が得られる場合を考える。 任意の整数 $\alpha \ge 1$ に対して、$f_i(S) \ge$(1-1/e^\alpha -\epsilon)b_i$ for each $i \in [r]$ と $\mathbb{E}[c(S)] \le (1+\epsilon)\alpha \cdot \sf{OPT}$ を出力するランダム化された二項近似アルゴリズムを得る。 第二に、f_i$ が削除閉集合系の重み付きカバレッジ関数であるとき、$(1+\epsilon)$$(\frac{e}{e-1})$(1+\beta)$-approximation を得る。 これらの結果は、固定された$r$の近似を$r=1$の近似とほぼ同等に得ることを示す。 これらの一般的な結果から簡単に追跡でき、将来もっと期待できるアプリケーションをいくつか紹介する。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• One-pass additive-error subset selection for $\ell_{p}$ subspace approximation [6.186553186139257]
  我々は $ell_p$ 部分空間近似に対する部分集合選択の問題を考える。 我々は、$ell_p$ subspace approximationの加算近似を保証した1パスのサブセット選択を与える。
  論文  参考訳（メタデータ） (2022-04-26T04:51:36Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• A closer look at the approximation capabilities of neural networks [6.09170287691728]
  1つの隠れた層を持つフィードフォワードニューラルネットワークは、任意の連続関数$f$を任意の近似しきい値$varepsilon$に近似することができる。 この均一な近似特性は、重量に強い条件が課せられているにもかかわらず、依然として維持されていることを示す。
  論文  参考訳（メタデータ） (2020-02-16T04:58:43Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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