論文の概要: A General Framework for Dynamic Consistent Submodular Maximization

• arxiv url: http://arxiv.org/abs/2606.04946v1
• Date: Wed, 03 Jun 2026 14:35:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 20:44:18.829486
• Title: A General Framework for Dynamic Consistent Submodular Maximization
• Title（参考訳）: 動的一貫した部分モジュラ最大化のための一般フレームワーク
• Authors: Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, Morteza Zadimoghaddam,
• Abstract要約: 一貫性は動的部分モジュラーアルゴリズムにおいて重要な性質である。 この設定のためのアルゴリズムを設計するための一般的なフレームワークを開発する。 濃度制約に対して、$frac 12 - O(varepsilon)$ approximation, $Oleft(frac1varepsilon2right)$ consistentを提案する。 階数-$k$ マトロイドの制約に対して、$frac 14 - O(varepsilon)$ を$Oleft(fraclog kvarepsilon2right)という動的最適化に近似する。
• 参考スコア（独自算出の注目度）: 29.25075734513064
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of $n$ insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a $\frac 12 - O(\varepsilon)$ approximation that is $O\left(\frac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\frac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\frac{\log k}{\varepsilon^2}\right)$ consistent.
• Abstract（参考訳）: 一貫性は動的部分モジュラーの最大化において重要な性質であり、常に最適に近い解を維持することを必要とし、各ステップで解にわずかな調整を与える。 それまでの研究では、アルゴリズムが$n$の挿入のストリームに直面する挿入専用の場合のこの問題を探求し、その問題の濃度制約バージョンに対する下限と上限を確立した。 この問題は、操作のストリームが挿入と削除の両方を含むことができる、完全に動的な設定で検討する。 この設定のためのアルゴリズムを設計するための一般的なフレームワークを開発し、それをインスタンス化し、サブ線形整合性を持つ最初の定数係数近似を得る。 濃度制約に対して、$O\left(\frac{1}{\varepsilon^2}\right)$一貫した$\frac 12 - O(\varepsilon)$近似を提案する。 階数-k$ マトロイドの制約に対して、$\frac 14 - O(\varepsilon)$ を$O\left(\frac{\log k}{\varepsilon^2}\right)$ 一貫性のある動的最適化に近似する。

関連論文リスト

• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  本研究では,有限状態空間を持つ無限水平割引決定過程(MD)に対して,単時間アクタークリティカル(AC)アルゴリズムのグローバル収束を解析する。 我々は,アクタと批評家の両方のステップサイズが (O(k-Pfrac12) として崩壊し,従来の (O(k-Pfrac12) ) レートから (非最適) の Markov フレームワーク最適化で一般的に使用される (O(k-Pfrac12) ) レートから$k$ になることを示した。
  論文  参考訳（メタデータ） (2024-10-11T14:46:29Z)
• Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
  我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。 本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
  論文  参考訳（メタデータ） (2024-05-20T02:24:58Z)
• Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
  マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。 本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。 マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-06-01T17:54:15Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
  濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。 これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
  論文  参考訳（メタデータ） (2021-11-05T00:04:29Z)
• Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
  まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。 第二に、完全適応部分モジュラリティの概念を導入する。 提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
  論文  参考訳（メタデータ） (2020-07-08T15:54:28Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。 次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
  論文  参考訳（メタデータ） (2020-06-21T06:57:59Z)

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

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