論文の概要: Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint

• arxiv url: http://arxiv.org/abs/2511.02254v1
• Date: Tue, 04 Nov 2025 04:37:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 18:47:05.812308
• Title: Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
• Title（参考訳）: サイズ制約下での非モノトンDR部分モジュラ最大化のための高速近似アルゴリズム
• Authors: Tan D. Tran, Canh V. Pham,
• Abstract要約: 本研究は,n$の基底集合上の非単調DR-部分モジュラー最大化を,サイズ制約付き$k$で研究する。 本稿では,FastDrSubとFastDrSub++という2つの近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 3.4806267677524896
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work studies the non-monotone DR-submodular Maximization over a ground set of $n$ subject to a size constraint $k$. We propose two approximation algorithms for solving this problem named FastDrSub and FastDrSub++. FastDrSub offers an approximation ratio of $0.044$ with query complexity of $O(n \log(k))$. The second one, FastDrSub++, improves upon it with a ratio of $1/4-\epsilon$ within query complexity of $(n \log k)$ for an input parameter $\epsilon >0$. Therefore, our proposed algorithms are the first constant-ratio approximation algorithms for the problem with the low complexity of $O(n \log(k))$. Additionally, both algorithms are experimentally evaluated and compared against existing state-of-the-art methods, demonstrating their effectiveness in solving the Revenue Maximization problem with DR-submodular objective function. The experimental results show that our proposed algorithms significantly outperform existing approaches in terms of both query complexity and solution quality.
• Abstract（参考訳）: 本研究は,n$の基底集合上の非単調DR-部分モジュラー最大化を,サイズ制約付き$k$で研究する。 本稿では,FastDrSubとFastDrSub++という2つの近似アルゴリズムを提案する。 FastDrSubは、クエリの複雑さが$O(n \log(k))$である0.044$の近似比を提供する。 2つめのFastDrSub++は、クエリの複雑さの中で1/4-\epsilon$の比率が$(n \log k)$の入力パラメータ$\epsilon > 0$で改善されている。 したがって,提案アルゴリズムは,$O(n \log(k))$の複雑さが低い問題に対する最初の定数比近似アルゴリズムである。 さらに、これらのアルゴリズムは既存の最先端手法と比較して実験的に評価され、DR-サブモジュラー目的関数を用いた収益最大化問題の解法の有効性を実証する。 実験の結果,提案アルゴリズムは問合せの複雑さと解の質の両方の観点から既存手法よりも優れていることがわかった。

関連論文リスト

• 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)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。 $mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-17T15:27:33Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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