Fugu-MT 論文翻訳(概要): Minimum Cost Adaptive Submodular Cover

論文の概要: Minimum Cost Adaptive Submodular Cover

arxiv url: http://arxiv.org/abs/2208.08351v1
Date: Wed, 17 Aug 2022 15:26:47 GMT
ステータス: 処理完了
システム内更新日: 2022-08-18 13:32:04.108546
Title: Minimum Cost Adaptive Submodular Cover
Title（参考訳）: 最小コスト適応サブモジュラカバー
Authors: Yubing Cui and Viswanath Nagarajan
Abstract要約: 適応部分モジュラ関数の最小コスト被覆の問題を考え,Qが目標値である4(ln Q+1)近似アルゴリズムを提案する。この問題に対する最初のO(ln Q)近似アルゴリズムである。
参考スコア（独自算出の注目度）: 4.84072817897891
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the problem of minimum cost cover of adaptive-submodular functions, and provide a 4(ln Q+1)-approximation algorithm, where Q is the goal value. This bound is nearly the best possible as the problem does not admit any approximation ratio better than ln Q (unless P=NP). Our result is the first O(ln Q)-approximation algorithm for this problem. Previously, O(ln Q) approximation algorithms were only known assuming either independent items or unit-cost items. Furthermore, our result easily extends to the setting where one wants to simultaneously cover multiple adaptive-submodular functions: we obtain the first approximation algorithm for this generalization.
Abstract（参考訳）: 適応サブモジュラー関数の最小コストカバーの問題を検討し、qを目標値とする4(ln q+1)近似アルゴリズムを提供する。この境界はほぼ最良であり、問題は ln q よりも近似比が良い(p=np でない)ことは認めない。その結果,この問題に対する最初のo(ln q)近似アルゴリズムが得られた。従来、o(ln q)近似アルゴリズムは独立アイテムか単位コストアイテムかを仮定してしか知られていなかった。さらに,複数の適応サブモジュラー関数を同時にカバーしたいという設定にも容易に拡張できる:この一般化のための最初の近似アルゴリズムを得る。

関連論文リスト

Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文参考訳（メタデータ） (2024-07-05T18:37:09Z)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
Partial-Monotone Adaptive Submodular Maximization [19.29174615532181]
サンプリングベースのポリシが近似比$(m+1)/10$ユーティリティ関数が$m$適応単調かつ適応部分モジュラーであることを示す。これにより、ユーティリティ機能がほぼ適応的なモノトンである多くの機械学習アプリケーションのバウンダリが改善される。
論文参考訳（メタデータ） (2022-07-26T12:16:12Z)
Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文参考訳（メタデータ） (2021-06-09T01:59:55Z)
The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文参考訳（メタデータ） (2021-04-06T20:25:57Z)
Approximation Algorithms for Active Sequential Hypothesis Testing [3.840659854046464]
本稿では,アクティブシーケンシャル仮説テストのための最初の近似アルゴリズムを提案する。アルゴリズムの性能を合成データと実データの両方を用いて数値的に調査し,アルゴリズムが提案した方針を上回っていることを示した。
論文参考訳（メタデータ） (2021-03-07T03:49:19Z)
Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文参考訳（メタデータ） (2021-02-23T18:25:13Z)
Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文参考訳（メタデータ） (2020-12-29T14:06:09Z)
Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。最適なデータ依存上界を導出する。また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文参考訳（メタデータ） (2020-08-12T15:40:21Z)
Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time [17.19443570570189]
濃度制約を受ける非単調適応部分モジュラー問題について検討する。適応的ランダムグリードアルゴリズムは適応的部分モジュラリティの下で1/e$の近似比を達成することを示す。我々は,$O(nepsilon-2log epsilon-1)$値オラクルクエリを期待して,1-1/e-epsilon$近似比を高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-08-11T21:06:52Z)

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