論文の概要: A Dynamic Algorithm for Weighted Submodular Cover Problem

• arxiv url: http://arxiv.org/abs/2407.10003v1
• Date: Sat, 13 Jul 2024 21:00:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-16 19:58:18.359419
• Title: A Dynamic Algorithm for Weighted Submodular Cover Problem
• Title（参考訳）: 重み付き部分モジュラ被覆問題に対する動的アルゴリズム
• Authors: Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh,
• Abstract要約: 基底集合の要素を挿入・削除する動的設定における部分モジュラー被覆問題について検討する。 本稿では,更新毎に多対数クエリの複雑さを用いてO(epsilon-1)$-bicriteria近似を求めるランダム化アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 11.354502646593607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of the submodular cover problem in dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, we are given a monotone submodular function $f : 2^{V} \to \mathbb{R}^{\ge 0}$ and the goal is to obtain a set $S \subseteq V$ that minimizes the cost subject to the constraint $f(S) = f(V)$. This is a classical problem in computer science and generalizes the Set Cover problem, 2-Set Cover, and dominating set problem among others. We consider this problem in a dynamic setting where there are updates to our set $V$, in the form of insertions and deletions of elements from a ground set $\mathcal{V}$, and the goal is to maintain an approximately optimal solution with low query complexity per update. For this problem, we propose a randomized algorithm that, in expectation, obtains a $(1-O(\epsilon), O(\epsilon^{-1}))$-bicriteria approximation using polylogarithmic query complexity per update.
• Abstract（参考訳）: 基底集合の要素を挿入・削除する動的設定における部分モジュラー被覆問題の研究を開始する。 古典的部分モジュラー被覆問題では、単調部分モジュラー函数 $f : 2^{V} \to \mathbb{R}^{\ge 0}$ が与えられ、その目標は、制約$f(S) = f(V)$ のコストを最小化する集合 $S \subseteq V$ を得ることである。 これはコンピュータ科学における古典的な問題であり、集合被覆問題、2セット被覆問題を一般化し、集合問題の中でも支配的な問題である。 我々は、この問題を、セットの$V$の更新が、基底セットの$\mathcal{V}$からの要素の挿入と削除の形で行われる動的な設定で考える。 そこで本研究では, 1-O(\epsilon), O(\epsilon^{-1}))$-bicriteria approximation を1回の更新に1-O(\epsilon), O(\epsilon^{-1}))$-bicriteria approximation というランダム化アルゴリズムを提案する。

関連論文リスト

• Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
  我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。 本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
  論文  参考訳（メタデータ） (2024-05-20T02:24:58Z)
• Dynamic Non-monotone Submodular Maximization [11.354502646593607]
  濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。 我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
  論文  参考訳（メタデータ） (2023-11-07T03:20:02Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
  マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。 本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。 マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-06-01T17:54:15Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Worst-Case Adaptive Submodular Cover [19.29174615532181]
  最悪の場合,適応的部分モジュラー被覆問題について検討する。 タイトな$(log (Q/eta)+1)$-approximationポリシーを開発します。 また、最悪の最大被覆問題も研究している。
  論文  参考訳（メタデータ） (2022-10-25T01:38:35Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
  濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。 これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
  論文  参考訳（メタデータ） (2021-11-05T00:04:29Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

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

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