論文の概要: Learning-Augmented Algorithms for Boolean Satisfiability

• arxiv url: http://arxiv.org/abs/2505.06146v1
• Date: Fri, 09 May 2025 15:54:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-12 20:40:10.323655
• Title: Learning-Augmented Algorithms for Boolean Satisfiability
• Title（参考訳）: ブール満足度向上のための学習補助アルゴリズム
• Authors: Idan Attias, Xing Gao, Lev Reyzin,
• Abstract要約: 古典的ブール満足度(SAT)決定と最適化問題を2種類のアドバイスを用いて検討する。 Subsetアドバイスは最適な代入から変数のランダムな$epsilon$区切りを提供するが、ラベルアドバイス”は最適な代入ですべての変数に対してノイズの多い予測を提供する。 最適化問題に対して、$alpha$-approximationアルゴリズムを用いて、サブセットアドバイスをブラックボックス方式で組み込む方法を示す。
• 参考スコア（独自算出の注目度）: 7.642039348547126
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning-augmented algorithms are a prominent recent development in beyond worst-case analysis. In this framework, a problem instance is provided with a prediction (``advice'') from a machine-learning oracle, which provides partial information about an optimal solution, and the goal is to design algorithms that leverage this advice to improve worst-case performance. We study the classic Boolean satisfiability (SAT) decision and optimization problems within this framework using two forms of advice. ``Subset advice" provides a random $\epsilon$ fraction of the variables from an optimal assignment, whereas ``label advice" provides noisy predictions for all variables in an optimal assignment. For the decision problem $k$-SAT, by using the subset advice we accelerate the exponential running time of the PPSZ family of algorithms due to Paturi, Pudlak, Saks and Zane, which currently represent the state of the art in the worst case. We accelerate the running time by a multiplicative factor of $2^{-c}$ in the base of the exponent, where $c$ is a function of $\epsilon$ and $k$. For the optimization problem, we show how to incorporate subset advice in a black-box fashion with any $\alpha$-approximation algorithm, improving the approximation ratio to $\alpha + (1 - \alpha)\epsilon$. Specifically, we achieve approximations of $0.94 + \Omega(\epsilon)$ for MAX-$2$-SAT, $7/8 + \Omega(\epsilon)$ for MAX-$3$-SAT, and $0.79 + \Omega(\epsilon)$ for MAX-SAT. Moreover, for label advice, we obtain near-optimal approximation for instances with large average degree, thereby generalizing recent results on MAX-CUT and MAX-$2$-LIN.
• Abstract（参考訳）: 学習強化アルゴリズムは、最悪のケース分析を越えて、最近の顕著な開発である。 このフレームワークでは、問題インスタンスに機械学習のオラクルからの予測(``advice'')が提供され、最適なソリューションに関する部分的な情報を提供する。 本稿では,2種類のアドバイスを用いて,従来の Boolean satisfiability (SAT) 決定と最適化問題について検討する。 ``Subset advice" は最適な代入から変数のランダムな$\epsilon$区切りを提供するが、 ``label advice" は最適な代入ですべての変数に対してノイズの多い予測を提供する。 決定問題$k$-SATの場合、サブセットアドバイスを使用することで、Paturi, Pudlak, Saks, Zane による PPSZ 系のアルゴリズムの指数的な実行時間を加速する。 実行時間を指数の基底の乗算係数$2^{-c}$で加速し、$c$は$\epsilon$と$k$の関数である。 最適化問題では、サブセットアドバイスを任意の$\alpha$-approximationアルゴリズムでブラックボックス方式に組み込む方法を示し、近似比を$\alpha + (1 - \alpha)\epsilon$に改善する。 具体的には、$0.94 + \Omega(\epsilon)$ for MAX-$2$-SAT, $/8 + \Omega(\epsilon)$ for MAX-$3$-SAT, $0.79 + \Omega(\epsilon)$ for MAX-SATとする。 さらに,ラベルアドバイスでは,平均値の高いインスタンスに対して近似近似値を求めるとともに,MAX-CUT および MAX-$2-LIN に関する最近の結果を一般化する。

関連論文リスト

• 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)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• 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)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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