論文の概要: Submodular Maximization under the Intersection of Matroid and Knapsack Constraints

• arxiv url: http://arxiv.org/abs/2307.09487v1
• Date: Tue, 18 Jul 2023 02:37:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-20 16:37:02.323224
• Title: Submodular Maximization under the Intersection of Matroid and Knapsack Constraints
• Title（参考訳）: マトロイドとクナプサックの界面における部分モジュラー最大化
• Authors: Yu-Ran Gu, Chao Bian and Chao Qian
• Abstract要約: 我々は、よく使われる2つの制約、すなわち$k$matroid 制約と $m$-knapsack 制約の交わる部分モジュラー演算の問題を考察する。 我々は、SPROUTOUTが最先端のアルゴリズムを組み込むよりも、SPR時間近似の保証を実現できることを証明した。 映画レコメンデーションと重み付きマックスカットの応用実験は、実際にSPROUT++の優位性を実証している。
• 参考スコア（独自算出の注目度）: 23.0838604893412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations research. Previous studies mainly consider only one kind of constraint, while many real-world problems often involve several constraints. In this paper, we consider the problem of submodular maximization under the intersection of two commonly used constraints, i.e., $k$-matroid constraint and $m$-knapsack constraint, and propose a new algorithm SPROUT by incorporating partial enumeration into the simultaneous greedy framework. We prove that SPROUT can achieve a polynomial-time approximation guarantee better than the state-of-the-art algorithms. Then, we introduce the random enumeration and smooth techniques into SPROUT to improve its efficiency, resulting in the SPROUT++ algorithm, which can keep a similar approximation guarantee. Experiments on the applications of movie recommendation and weighted max-cut demonstrate the superiority of SPROUT++ in practice.
• Abstract（参考訳）: サブモジュールの最大化は多くの応用で起こり、人工知能、金融、オペレーション研究など様々な分野から多くの研究の注目を集めている。 従来の研究は主に1種類の制約しか考慮していなかったが、現実の問題の多くはいくつかの制約を伴っている。 本稿では,2つの一般的な制約,すなわち$k$-matroid 制約と $m$-knapsack 制約の交点における部分モジュラ最大化の問題を考察し,部分列挙を同時グリードフレームワークに組み込んだ新しいアルゴリズム SPROUT を提案する。 我々はsproutが最先端アルゴリズムよりも多項式時間近似の保証を実現できることを証明した。 次に,SPROUTにランダム列挙とスムーズな手法を導入して効率を向上し,SPROUT++アルゴリズムにより同様の近似を保証する。 映画レコメンデーションと加重マックスカットの応用実験は、実際にSPROUT++の優位性を実証している。

関連論文リスト

• Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
  Submodularは、人工知能の分野における様々な分野に広く応用されている。 部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。 証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
  論文  参考訳（メタデータ） (2023-08-21T11:48:34Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-28T23:18:58Z)
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms [16.691265882753346]
  GSEMOと呼ばれる単純な進化的アルゴリズムは、部分モジュラ函数の近似を効率的に行うことが示されている。 我々は理論結果を拡張し、濃度制約を一般化するマトロイド制約を分割する。
  論文  参考訳（メタデータ） (2020-06-23T05:37:29Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。 解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。 我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
  論文  参考訳（メタデータ） (2020-06-16T17:06:45Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
  我々は、$l$knapsacksと$k$-system制約の交わりの下で、部分モジュラーバンディット問題を導入する。 この問題を解決するために,標準あるいは修正された高信頼境界に適応的に焦点をあてる非グレーディアルゴリズムを提案する。 近似比が高速アルゴリズムのそれと一致するような近似後悔の確率の高い上限を提供する。
  論文  参考訳（メタデータ） (2020-06-01T01:28:44Z)

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

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