DS-1-6 A Message Passing Algorithm for MAX2SAT

スポンサーリンク

概要

• 論文の詳細を見る

• We propose a simple and deterministic algorithm for solving MAX2SAT, which runs O(n(n+m)) time where n and m are respectively the number of variables and clauses. For discussing its average case performance, we propose one natural "planted solution model"; a way to generate a MAX2SAT instance under a certain distribution defined by parameters p and r. We first show that if p=Ω(ln^2n/n) and p≥9r, then with high probability the planted solutions (there are four planted solutions) are only the optimal solution, unsatisfying 3rn^2 clauses out of (on average) 2pn^2+8rn^2 clauses. Then under this planted solution model we show that, for some constant ε>0, our algorithm yields one of the planted solutions with high probability if p-r≥n^<-1/2+ε>.

• 2006-03-08

著者

• Yamamoto Masaki

  Dept. Of Math. And Comp. Sci. Tokyo Inst. Of Technology

• Watanabe Osamu

  Dept. Computer Science Tokyo Institute Of Technology

関連論文

• Pseudo Expectation : A Tool for Analyzing Local Search Algorithms
• DS-1-7 On Coppersmith's Technique and its Limit
• On Polynomial Time Many-One Completeness of One-Way Functions : Preliminary Report
• Spectral Analysis of Random Sparse Matrices
• The Relation between Time and Accepting Probability on Probabilistic Simple Decision Trees : Extended abstract(Mathematical Theories on Computing Schemes and Their Applications)
• A planted solution model for the MAX-2SAT problem (情報物理学の数学的構造--RIMS研究集会報告集)
• DS-1-6 A Message Passing Algorithm for MAX2SAT
• An O(n^)-Space and Polynomial-Time Algorithm for Directed Planar Reachability

スポンサーリンク