Art

J-GLOBAL ID：200902215920847607   Reference number：06A0498407

Average-case Analysis for the MAX-2SAT Problem

MAX-2SAT問題の平均時間計算量の解析

Author (2)： WATANABE Osamu (Tokyo Inst. Technol., Tokyo, JPN) ,  YAMAMOTO Masaki (Tokyo Inst. Technol., Tokyo, JPN)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 106  Issue： 63(COMP2006 10-16)  Page： 25-32  Publication year： May. 17, 2006 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *satisfiability problem ,...
Semi thesaurus term： *computational complexity ,...

   To see more with JDream III (charged).   {{ this.onShowAbsJLink("http://jdream3.com/lp/jglobal/index.html?docNo=06A0498407&from=J-GLOBAL&jstjournalNo=S0532B") }}

JST classification (3)： Logic algebra  (JB03000H) ,  Theory of computation  (JB02000A) ,  System and control theory in general  (IA02010H)

Reference (11)：

• BOUGHACI, D. Efficient and experimental meta-heuristics for MAX-SAT problems. Proc. Workshop on Experimental/Efficient Algorithms, 2005. 2005, 501-512
• DRIAS, H. Scatter search with walk strategy for solving hard Max-W-Sat problems. Proc. of Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 2001. 2001, 35-44
• HASTAD, J. Some optimal inapproximability results. Journal of the ACM. 2001, 48, 798-859
• MAZURE, B. A tabu search for sat. Proc. of the 15th National Conf. on Artificial Intelligence (AAAI97). 1997, 281-285
• MCDIARMID, C. Concentration. Probabilistic Methods for Algorithmic Discrete Mathematics. 1998

Terms in the title (5)： Max ,  問題 ,  平均 ,  時間計算量 ,  解析