zbMATH — the first resource for mathematics

A new upper bound for Max-2-SAT: A graph-theoretic approach. (English) Zbl 1203.90130
Summary: In MaxSat, we ask for an assignment to the variables which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of \(O^*(2^{\frac{K}{6.265}})\) for Max-2-Sat (each clause contains at most 2 literals), where \(K\) is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. The analysis uses a non-standard measure.

90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI
[1] Fernau, H.; Raible, D., Searching trees: an essay, (), 59-70 · Zbl 1241.68058
[2] Fomin, F.V.; Grandoni, F.; Kratsch, D., A measure & conquer approach for the analysis of exact algorithms, Journal of the ACM, 56, 5, (2009) · Zbl 1325.68311
[3] Gaspers, S.; Sorkin, G.B., A universally fastest algorithms for MAX 2-sat, MAX 2-CSP, and everything in between, (), 606-615 · Zbl 1238.68066
[4] Gramm, J.; Hirsch, E.A.; Niedermeier, R.; Rossmanith, P., Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete applied mathematics, 130, 139-155, (2003) · Zbl 1051.68078
[5] Gramm, J.; Niedermeier, R., Faster exact solutions for MAX2SAT, (), 174-186 · Zbl 0971.68598
[6] Hofmeister, T., An approximation algorithm for MAX-2-SAT with cardinality constraint, (), 301-312 · Zbl 1266.68229
[7] Kneis, J.; Mölle, D.; Richter, S.; Rossmanith, P., Algorithms based on the treewidth of sparse graphs, (), 385-396 · Zbl 1171.05428
[8] Kojevnikov, A.; Kulikov, A.S., A new approach to proving upper bounds for MAX-2-SAT, (), 11-17 · Zbl 1192.68368
[9] Kulikov, A.S.; Kutzkov, K., New bounds for \scmax-\scsat by clause learning, (), 194-204 · Zbl 1188.68272
[10] Kulikov, A.S.; Kutzkov, K., New upper bounds for the problem of maximal satisfiability, Journal of discrete mathematics and applications, 19, 155-172, (2009) · Zbl 1234.68154
[11] Lewin, M.; Livnat, D.; Zwick, U., Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems, (), 67-82 · Zbl 1049.90535
[12] Li, C.M.; Manyà, F.; Mohamedou, N.O.; Planes, J., Exploiting cycle structures in MAX-SAT, (), 467-480 · Zbl 1247.68256
[13] Li, C.M.; Manyà, F.; Planes, J., New inference rules for MAX-SAT, Journal of artificial intelligence research, 30, 321-359, (2007) · Zbl 1182.68254
[14] Niedermeier, R., Invitation to fixed-parameter algorithms, (2006), Oxford University Press Oxford · Zbl 1095.68038
[15] Niedermeier, R.; Rossmanith, P., New upper bounds for maximum satisfiability, Journal of algorithms, 36, 63-88, (2000) · Zbl 0959.68049
[16] Palubeckis, G., A new bounding procedure and an improved exact algorithm for the MAX-2-SAT problem, Applied mathematics and computation, 215, 3, 1106-1117, (2009) · Zbl 1179.90234
[17] S. Poljak, Z. Tuza, Maximum cuts and largest bipartite subgraphs, in: W. Cook, L. Lovász, P. Seymour, (Eds.), Combinatorial Optimization, in: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 20, 1995, pp. 181-244. · Zbl 0834.05001
[18] Scott, A.D.; Sorkin, G.B., Linear-programming design and analysis of fast algorithms for MAX 2-CSP, Discrete optimization, 4, 3-4, 260-287, (2007) · Zbl 1153.90505
[19] Williams, R., A new algorithm for optimal 2-constraint satisfaction and its implications, Theoretical computer science, 348, 2-3, 357-365, (2005) · Zbl 1081.68095
[20] Yannakakis, M., On the approximation of maximum satisfiability, Journal of algorithms, 17, 3, 475-502, (1994) · Zbl 0820.68056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.