論文の概要: Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT

• arxiv url: http://arxiv.org/abs/2610.39992v1
• Date: Thu, 29 Oct 2026 13:12:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-01 01:32:10.086496
• Title: Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT
• Title（参考訳）: プルーニング制約の累積化: Max 2-SAT のための厳密な多項式空間アルゴリズム
• Abstract要約: 正確には$n$変数上でMax 2-SATを解く決定論的空間アルゴリズムを提案する。 当社のツールは,従来のDPLL分岐アルゴリズムを拡張しています。
• 参考スコア（独自算出の注目度）: 3.655021726150368
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present deterministic polynomial-space algorithms that solve Max 2-SAT on $n$ variables exactly in time $\Ostar(2^{(1-γ)n})$, for a fixed $γ>0$, on several classes of instances whose clause density may grow with $n$. Our main tool extends the classic DPLL branching algorithm. When the search gives a variable its less promising value, comparing the two values of the variable yields a pruning constraint that is satisfied by some optimal assignment. Accumulating these constraints along each branch prunes all but an exponentially small fraction of the assignments. The classes are formulas with many biased variables, semirandom 2-CNF formulas, and Max-Cut on regular expander graphs and on graphs generated by a stochastic block model. In a semirandom formula, the pairs of variables that may share a clause are arbitrary, and the clauses on these pairs are random. For semirandom formulas and block-model graphs, the algorithms are still exact on every input, and the time bound holds with high probability over the input. To our knowledge, these are the first polynomial-space algorithms with such a running time for nontrivial classes of dense Max 2-SAT instances. Beyond these classes, the pruning constraints can be added to any branching algorithm for Max 2-SAT, and we expect them to be of practical relevance for general formulas, in particular for sparse ones, where each constraint involves only a few variables.
• Abstract（参考訳）: 固定された$γ>0$に対して、$n$変数のMax 2-SATを正確に時間$\Ostar(2^{(1-γ)n})$で解く決定論的多項式空間アルゴリズムを提案する。 当社のツールは,従来のDPLL分岐アルゴリズムを拡張しています。 探索が変数に期待できない値を与えるとき、変数の2つの値を比較すると、最適な割り当てによって満たされるプルーニング制約が得られる。 これらの制約を各枝のプルーヌに沿って累積すると、割り当ての指数的に小さな部分しか得られない。 クラスは、多くのバイアス変数、半ランダムな2-CNF式、および正則拡大グラフ上のMax-Cutおよび確率ブロックモデルによって生成されるグラフを持つ公式である。 半ランダム式では、節を共有する変数のペアは任意であり、これらのペアの節はランダムである。 半ランダム式やブロックモデルグラフの場合、アルゴリズムは入力毎に正確であり、時間境界は入力に対して高い確率で保持される。 我々の知る限り、これらは密度の高いMax 2-SATインスタンスの非自明なクラスに対してそのような実行時間を持つ最初の多項式空間アルゴリズムである。 これらのクラス以外にも、プルーニングの制約はMax 2-SATの任意の分岐アルゴリズムに追加することができ、一般公式、特にスパース式において、各制約が数変数のみを含むような実効的な妥当性を期待する。

関連論文リスト

• 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)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
  論文  参考訳（メタデータ） (2024-12-30T18:59:46Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
  制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。 アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
  論文  参考訳（メタデータ） (2024-05-08T16:39:59Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• The Algorithmic Phase Transition of Random $k$-SAT for Low Degree Polynomials [18.00315760946089]
  満足な代入は、節密度$m/n 2k log 2 - frac12で高い確率で存在することが知られている。 低次アルゴリズムは節密度$(1 - o_k(1)) 2k log k / k$で満足な代入を見つけることができる。
  論文  参考訳（メタデータ） (2021-06-03T21:01:02Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT [0.0]
  本稿では,最大3-Stisfiability (MAX-E-$3$-SAT) 問題に対して$Theta(N)$で近似解を計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-10T07:59:54Z)

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

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