Approximating Backbone in the Weighted Maximum Satisfiability Problem

摘要：

The weighted Maximum Satisfiability problem (weighted MAXSAT) is a NP-hard problem with numerous applications arising in artificial intelligence. As an efficient tool for heuristic design, the backbone has been applied to heuristics design for many NP-hard problems. In this paper, we investigated the computational complexity for retrieving the backbone in weighted MAX-SAT. We showed that it is intractable to retrieve the full backbone under the assumption that P ≠ NP. Moreover,it is intractable to retrieve a fixed fraction of the backbone as well. And then we demonstrated that the backbone can be efficiently approximated by the common part of local optima.

作者: He Jiang Ji-Feng Xuan Yan Hu

作者单位: School of Software,Dalian University of Technology,116621 Dalian,China;The State Key Laboratory of C School of Software,Dalian University of Technology,116621 Dalian,China

会议类型: 国际会议

会议名称: The Inaugural Symposium on Parallel Algorithms, Architectures and Programming(并行算法、结构和编程国际研讨会)

会议地点: 广州

会议语种:英文

页码: 80-93

在线出版日期: 2008-09-16（万方平台首次上网日期，不代表论文的发表时间）