論文の概要: 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)近似アルゴリズムは独立アイテムか単位コストアイテムかを仮定してしか知られていなかった。
さらに,複数の適応サブモジュラー関数を同時にカバーしたいという設定にも容易に拡張できる:この一般化のための最初の近似アルゴリズムを得る。
関連論文リスト
- Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T14:37:21Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular
Maximization in Parallel [32.5364938726281]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳(メタデータ) (2021-11-15T17:10:40Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文 参考訳(メタデータ) (2021-02-16T18:15:51Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳(メタデータ) (2021-02-12T12:38:03Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳(メタデータ) (2020-08-12T15:40:21Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳(メタデータ) (2020-07-08T15:54:28Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。