論文の概要: Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem

• arxiv url: http://arxiv.org/abs/2511.00869v1
• Date: Sun, 02 Nov 2025 09:39:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 16:37:26.972313
• Title: Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
• Title（参考訳）: $k$-submodular Cover問題に対する高速確率グリーディアルゴリズム
• Authors: Hue T. Nguyen, Tan D. Tran, Nguyen Long Giang, Canh V. Pham,
• Abstract要約: 既存の$k$SCのアルゴリズムは、しばしば弱い近似保証を提供する。 提案手法は,機能評価の回数を削減し,大規模実世界のアプリケーションに対して高いスケーラビリティと実用性を実現する。
• 参考スコア（独自算出の注目度）: 2.8348950186890467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the $k$-Submodular Cover ($kSC$) problem, a natural generalization of the classical Submodular Cover problem that arises in artificial intelligence and combinatorial optimization tasks such as influence maximization, resource allocation, and sensor placement. Existing algorithms for $\kSC$ often provide weak approximation guarantees or incur prohibitively high query complexity. To overcome these limitations, we propose a \textit{Fast Stochastic Greedy} algorithm that achieves strong bicriteria approximation while substantially lowering query complexity compared to state-of-the-art methods. Our approach dramatically reduces the number of function evaluations, making it highly scalable and practical for large-scale real-world AI applications where efficiency is essential.
• Abstract（参考訳）: 我々は、人工知能や、影響の最大化、資源配分、センサ配置といった組合せ最適化タスクで発生する古典的部分モジュラカバー問題の自然な一般化である、$k$-submodular Cover(kSC$)問題について研究する。 既存の$\kSC$のアルゴリズムは、しばしば弱い近似保証を提供する。 これらの制限を克服するため,従来の手法に比べてクエリの複雑さを著しく低減しつつ,強い双クリテリア近似を実現する。 当社のアプローチは機能評価の数を劇的に削減し,効率性が不可欠である大規模実世界のAIアプリケーションに対して,高度にスケーラブルで実用的なものにしている。

関連論文リスト

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
  本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。 我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
  論文  参考訳（メタデータ） (2024-09-06T17:17:52Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Adaptive Sampling for Fast Constrained Maximization of Submodular Function [8.619758302080891]
  非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。 本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
  論文  参考訳（メタデータ） (2021-02-12T12:38:03Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• A PAC algorithm in relative precision for bandit problem with costly sampling [0.0]
  本稿ではまず,この離散最適化問題に対して,相対的精度でほぼ正解(PAC)を得るための単純帯域幅アルゴリズムを提案する。 また、同一の保証付きPACソリューションを提供する適応的帯域幅アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-30T09:22:25Z)
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint [13.357957711519134]
  制約されたサブモジュール問題には、パーソナライズされたレコメンデーション、チーム形成、バイラルマーケティングによる収益化など、さまざまな応用が含まれている。 我々は5.83のランダム化近似を達成し、O(n log n)$禁断時間、すなわち少なくとも$n$を他の最先端アルゴリズムよりも高速に実行する単純なグリーディアルゴリズムを提案する。 そこで我々は,非単調な目的に対する最初の定数近似である9-近似を求め,実データと合成データに改良された性能を示すアルゴリズムの実験評価を行った。
  論文  参考訳（メタデータ） (2020-07-09T18:15:01Z)

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

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