[1]谷文祥,姜蕴晖,周俊萍,等.最坏情况下Min-2SAT问题的上界[J].智能系统学报,2012,7(3):241-245.
 GU Wenxiang,JIANG Yunhui,ZHOU Junping,et al.New worstcase upper bounds for Min-2SAT problems[J].CAAI Transactions on Intelligent Systems,2012,7(3):241-245.
点击复制

最坏情况下Min-2SAT问题的上界

参考文献/References:
[1]HANSEN P, JAUMARD B. Algorithms for the maximum satisfiability problem[J]. Computing, 1990, 44(4): 279303.
[2]WALLACE R J. Enhancing maximum satisfiability algorithms with pure literal strategies[C]//Proceedings of the 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence. London, UK: SpringerVerlag, 1996: 388401.
[3]NIEDERMEIER R, ROSSMANITH P. New upper bounds for MaxSat[C]//Proceedings of the 26th International Colloquium on Automata, Languages and Programming. London, UK: SpringerVerlag, 1999: 575584.
[4]GRAMM J, HIRSCH E A, NIEDERMEIER R, et al. Worstcase upper bounds for MAX2SAT with an application to MAXCUT[J]. Discrete Applied Mathematics, 2003, 130(2): 139155.
[5]KNEIS J, ROSSMANITH P. A new satisfiability algorithm with applications to MaxCut: Technical Report AIB200508[R]. Aachen, Germany: Department of Computer Science, RWTH Aachen University, 2005.
[6]KULIKOV A S, KUTZKOV K. New bounds for MAXSAT by clause learning[C]//2nd International Symposium on Computer Science in Russia. Ekaterinburg, Russia, 2007: 194204.
[7]BINKELERAIBLE D, FERNAU H. A new upper bound for Max2SAT: a graphtheoretic approach[J]. Journal of Discrete Algorithms, 2010, 8(4): 388401.
[8]GASPERS S, SORKIN G B. A universally fastest algorithm for Max 2Sat, Max 2CSP, and everything in between[J]. Journal of Computer and System Sciences, 2012, 78(1): 305335.
[9]AVIDOR A, ZWICK U. Approximating MIN 2SAT and MIN 3SAT[J]. Theory of Computing Systems, 2005, 38(3): 329345.
[10]MARATHE M V, RAVI S S. On approximation algorithms for the minimum satisfiability problem[J]. Information Processing Letters, 1996, 58(1): 2329.
[11]LI Chumin, MANYA F, QUAN Zhe, et al. Exact MinSAT solving[C]//Proceedings of the 13th International Conference on Theory and Applications of Satisfiability Testing. Berlin/Heidelberg, Germany: SpringerVerlag, 2010: 363368.
[12]ZHOU Junping, YIN Minghao, ZHOU Chunguang. New worstcase upper bound for #2SAT and #3SAT with the number of clauses as the parameter[C]//Proceedings of the TwentyFourth AAAI Conference on Artificial Intelligence. Atlanta, USA, 2010. 
[13]KOJEVNIKOV A, KULIKOV A S. A new approach to proving upper bounds for MAX2SAT[C]//Proceedings of the Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms. New York, USA: ACM, 2006: 1117.

备注/Memo

收稿日期: 2011-09-06.网络出版日期:2012-05-10.
基金项目:国家自然科学基金资助项目(61070084);国家自然科学青年基金资助项目(60803102);中央高校基本科研业务费专项资金资助项目(11QNJJ006).
通信作者:姜蕴晖.E-mail: jiangyh215@nenu.edu.cn.
作者简介:
谷文祥,男,1947年生,教授,博士生导师,主要研究方向为智能规划与规划识别.主持或参与国家自然科学基金项目5项、教育部重点项目2项、省科委项目1项.发表学术论文130余篇,出版专著《智能规划与规划识别》,2011年获得吉林省专著类一等奖.
姜蕴晖,女,1987年生,硕士研究生,主要研究方向为智能规划与自动推理.
周俊萍,女,1981年生,讲师,主要研究方向为智能规划与自动推理,发表学术论文5篇.

更新日期/Last Update: 2012-09-05
Copyright © 《 智能系统学报》 编辑部
地址:(150001)黑龙江省哈尔滨市南岗区南通大街145-1号楼 电话:0451- 82534001、82518134 邮箱:tis@vip.sina.com