論文の概要: A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

• arxiv url: http://arxiv.org/abs/2609.09986v1
• Date: Wed, 09 Sep 2026 10:13:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.985936
• Title: A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse
• Title（参考訳）: 連続部分モジュラー最大化のためのシャープバリア: 2-\sqrt{2}$以上の改善
• Abstract要約: 我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
• 参考スコア（独自算出の注目度）: 50.69285844345291
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most $k$ available elements and changes only $O(1)$ elements after each insertion. Dütting et al. [2025] established a tight $2/3$ approximation with unrestricted computation and a polynomial-time $0.51$ approximation. They left open at STOC 2025 whether efficient algorithms can match the offline $1-1/e$ guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is \[ β=2-\sqrt2\approx0.5858<1-1/e. \] For every $\varepsilon>0$, our randomized algorithm attains $β-\varepsilon$ with $O(\varepsilon^{-2})$ changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of $Ω(k)$ changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold $1-(\sqrt2-1)\vartheta$, attain $1-1/e-\varepsilon$ for weighted coverage with $O(\varepsilon^{-1})$ recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.
• Abstract（参考訳）: 連続部分モジュラー最大化(英語版)は、要素が時間とともに到着する際の解の質と安定性の間のトレードオフを研究する。 モデルがリターンを減少させるモノトン部分モジュラー対象に対して、アルゴリズムは少なくとも$k$の利用可能な要素のセットを保持し、挿入後にO(1)$の要素だけを変更する。 Dütting et al [2025] は、厳密な 2/3$ 近似と、制限のない計算と多項式時間0.51$ 近似を確立した。 彼らはSTOC 2025で、効率的なアルゴリズムがオフラインの1-1/e$保証と一致するかどうかを公表した。 この問題は、多項式的に多くの値クエリと最悪のケースの定数リコースで得られる上限近似が \[ β=2-\sqrt2\approx0.5858<1-1/e] であることを証明することで解決する。 \] $\varepsilon>0$に対して、我々のランダム化アルゴリズムは$β-\varepsilon$と$O(\varepsilon^{-2})$を挿入毎に変更する。 任意の固定された改善は、1つの臨界挿入または1つの臨界挿入またはリニアリコースの前に指数関数的に多くのクエリを必要とする。 このギャップは一貫性のコストを定量化します。現在のオラクルは到着後に必要な要素を隠蔽します。 O(\varepsilon^{-1})$ recourseで重み付きカバレッジが1-1/e-\varepsilon$に達することで、正確な曲率依存しきい値が1-(\sqrt2-1)\vartheta$を決定できる。 我々のアルゴリズムは、多項式ビット有理オラクル解に対する有界ビット多項式時実装を持ち、下限は対数ビット有理解のみを使用する。

関連論文リスト

• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications [13.39372872460586]
  mathbbRn times d$ の行列 $X の 2 つの右幅 q$ノルムは $lVert X rVert_2 rightarrow q = sup_lVert v rVert = 1 lVert Xv rVert_q$ と定義される。 FOCS(Exponential Time hypothesis)を仮定すると、単純なスペクトルアルゴリズムは2sqrtlog n$よりも近似係数がよいことを示す。
  論文  参考訳（メタデータ） (2026-05-24T23:56:06Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• 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)
• 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)
• 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)

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

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