A new approach to proving upper bounds for MAX-2-SAT
作者： Arist Kojevnikov , Alexander S. Kulikov
关键词:
摘要: In this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (MAX-2-SAT). We 2K/5.5-time algorithm MAX-2-SAT, where K is number of clauses in an input formula. also obtain 2N/6 bound, N variables formula, particular case each variable appears at most three 2-clauses. This immediately implies vertices graph, independent set on 3-regular graphs. The key point our improvement combined complexity measure estimating running time algorithm. By using are able provide much simpler proof MAX-2-SAT than proofs previously known bounds.
acm.org
sci-hub.st 参考文章(14)
Joachim Kneis, Peter Rossmanith, A New Satisabilit y Algorithm With Applications To Max-Cut ,(2005)
Svatopluk Poljak, Zsolt Tuza, Maximum cuts and largest bipartite subgraphs. Combinatorial Optimization. pp. 181- 244 ,(1993)
Jianer Chen, Iyad A. Kanj, Improved Exact Algorithms for MAX-SAT latin american symposium on theoretical informatics. pp. 341- 355 ,(2002) , 10.1007/3-540-45995-2_32
Alexander S. Kulikov, Automated Generation of Simplification Rules for SAT and MAXSAT Theory and Applications of Satisfiability Testing. ,vol. 3569, pp. 430- 436 ,(2005) , 10.1007/11499107_35
Sergey S. Fedin, Alexander S. Kulikov, Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms Parameterized and Exact Computation. ,vol. 134, pp. 248- 259 ,(2004) , 10.1007/978-3-540-28639-4_22
Nikhil Bansal, Venkatesh Raman, Upper Bounds for MaxSat: Further Improved international symposium on algorithms and computation. pp. 247- 258 ,(1999) , 10.1007/3-540-46632-0_26
Patrizia Asirelli, Michelle De Santis, Maurizio Martelli, Integrity constraints in logic databases Journal of Logic Programming. ,vol. 2, pp. 221- 232 ,(1985) , 10.1016/0743-1066(85)90020-2
Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT Discrete Applied Mathematics. ,vol. 130, pp. 139- 155 ,(2003) , 10.1016/S0166-218X(02)00402-X
Venkatesh Raman, B. Ravikumar, S.Srinivasa Rao, A simplified NP-complete MAXSAT problem Information Processing Letters. ,vol. 65, pp. 1- 6 ,(1998) , 10.1016/S0020-0190(97)00223-8
O. Kullmann, New methods for 3-SAT decision and worst-case analysis Theoretical Computer Science. ,vol. 223, pp. 1- 72 ,(1999) , 10.1016/S0304-3975(98)00017-6