論文の概要: Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint
- arxiv url: http://arxiv.org/abs/2008.05391v2
- Date: Wed, 13 Jan 2021 15:53:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-31 05:57:11.333846
- Title: Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint
- Title（参考訳）: knapsack 制約付き単調部分モジュラー最大化のための修正greedyアルゴリズムの再検討
- Authors: Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, Junsong
Yuan
- Abstract要約: 修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
- 参考スコア（独自算出の注目度）: 75.85952446237599
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Monotone submodular maximization with a knapsack constraint is NP-hard.
Various approximation algorithms have been devised to address this optimization
problem. In this paper, we revisit the widely known modified greedy algorithm.
First, we show that this algorithm can achieve an approximation factor of
$0.405$, which significantly improves the known factors of $0.357$ given by
Wolsey and $(1-1/\mathrm{e})/2\approx 0.316$ given by Khuller et al. More
importantly, our analysis closes a gap in Khuller et al.'s proof for the
extensively mentioned approximation factor of $(1-1/\sqrt{\mathrm{e}})\approx
0.393$ in the literature to clarify a long-standing misconception on this
issue. Second, we enhance the modified greedy algorithm to derive a
data-dependent upper bound on the optimum. We empirically demonstrate the
tightness of our upper bound with a real-world application. The bound enables
us to obtain a data-dependent ratio typically much higher than $0.405$ between
the solution value of the modified greedy algorithm and the optimum. It can
also be used to significantly improve the efficiency of algorithms such as
branch and bound.
- Abstract（参考訳）: クナップサック制約付きモノトンサブモジュラー最大化はnpハードである。
この最適化問題に対処するために様々な近似アルゴリズムが考案された。
本稿では,広く知られている改良グレディアルゴリズムを再検討する。
まず、このアルゴリズムが0.405$の近似係数を達成できることを示し、wolseyが与えた0.357$と、khullerらによって与えられた$(1-1/\mathrm{e})/2\approx 0.316$の既知の因子を大幅に改善する。
より重要なことに、我々の分析は、この問題に対する長年の誤解を明らかにするために文献に約0.393ドルの近似係数(1-1/\sqrt{\mathrm{e}})\ に関するkhullerらの証明のギャップを閉じている。
第2に,修正グリーディアルゴリズムを拡張し,最適なデータ依存上界を導出する。
私たちは実世界のアプリケーションで上界の厳密さを実証的に示します。
このバウンドにより、修正グリーディアルゴリズムの解値と最適解の間で、典型的には$0.405$よりもずっと高いデータ依存比が得られる。
分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使用できる。
関連論文リスト
- Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。
アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
論文 参考訳（メタデータ） (2024-05-08T16:39:59Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Fast algorithms for k-submodular maximization subject to a matroid
constraint [10.270420338235237]
マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。
我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-07-26T07:08:03Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - 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 Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。