論文の概要: Consistent Submodular Maximization with Full Foresight

• arxiv url: http://arxiv.org/abs/2611.06223v1
• Date: Wed, 04 Nov 2026 09:32:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:58.044253
• Title: Consistent Submodular Maximization with Full Foresight
• Title（参考訳）: フルフォアビジョンによる一貫した部分モジュラ最大化
• Abstract要約: 単調な部分モジュラーアルゴリズムは、少なくとも$k$の到着した要素の解をステップごとに一定数の変化で維持しなければならない。 我々は、将来のリコースの準備と現在の解決策の保護という、2つの対立する力を最適にバランスさせる。 乱数化アルゴリズムでは、未知の未来の接頭辞に対する付加ロバスト性を使用し、間隔選択問題を通じて厳密に解析する。
• 参考スコア（独自算出の注目度）: 32.804629137971894
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$, we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.
• Abstract（参考訳）: 有界なリコースを持つオンラインアルゴリズムは、未来に対する不確実性、計算限界、変化のための限られた予算の3つの障害に直面している。 私たちは、一貫性を他の2つから分離する根本的な疑問を問う。 未来全体が知られ、計算が無制限である場合、ソリューションの安定性は、何にコストがかかるのか? 単調な部分モジュラー最大化(英語版)では、アルゴリズムは最低でも$k$の到着要素の解をステップ毎に一定数の変化で維持しなければならない。 決定論的アルゴリズムは3/4$、ランダムアルゴリズムは0.7942$である。 for every $\varepsilon>0$, we get within $\varepsilon$ in the thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length。 カバレッジ関数においても,一致しない結果が証明される。 我々は、2つの対立する力を最適にバランスさせ、将来の到着に備え、現在の解決策を保護することで、鋭い境界を得る。 乱数化アルゴリズムでは、既知の未来の接頭辞に対する付加ロバスト性を使用し、インターバルセレクション問題を用いて厳密に解析する。 決定論的アルゴリズムでは、高い価値を維持する分数緩和の証明書やパスを導入し、それを更新スケジュールにまとめます。

関連論文リスト

• Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff [0.5922488908114023]
  最終的な最適解法として,オンライン区間選択を二元予測を用いて検討する。 報酬が区間長に比例すると、有限厳密性の下での最良の整合性は$d=(3+sqrt5)/2$である。
  論文  参考訳（メタデータ） (2026-10-27T14:56:43Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• The Cost of Consistency: Submodular Maximization with Constant Recourse [30.724711970113777]
  特に,アルゴリズムが1ステップあたりの更新回数を最大で一定にした場合に達成可能な,最も有望な近似比を求める。 我々は、一般的な部分モジュラ函数に対して$tfrac23$の厳密な情報理論境界と、カバレッジ関数に対して$tfrac34$の改良された(かつ厳密な)境界を示す。
  論文  参考訳（メタデータ） (2024-12-03T15:06:07Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Simultaenous Sieves: A Deterministic Streaming Algorithm for Non-Monotone Submodular Maximization [16.346069386394703]
  定性制約に関して、必ずしも単調ではない部分モジュラ函数を最大化する問題に対して、決定論的でシングルパスのストリーミングアルゴリズムを提案する。 単調でシングルパスのストリーミングアルゴリズムでは,従来の文献の1/9ドルから0.2689ドルまで,最高の近似係数の改善を実現している。
  論文  参考訳（メタデータ） (2020-10-27T15:22:49Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)

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

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