zbMATH — the first resource for mathematics

An empirical study of Max-2-sat phase transitions. (English) Zbl 1179.68148
Kranakis, Evangelos (ed.) et al., Typical case complexity and phase transitions. Papers from the workshop, Ottawa, ON, Canada, May 14–16, 2003. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 16, 80-92 (2003).
Summary: The decision version of the maximum satisfiability problem (MAX-SAT) is stated as follows: Given a set \(S\) of propositional clauses and an integer \(g\), decide if there exists a truth assignment that falsifies at most \(g\) clauses in \(S\), where g is called the allowance for false clauses. We conduct an extensive experiment on over a million of random instances of 2-SAT and identify statistically the relationship between \(g, n\) (number of variables) and m (number of clauses). In our experiment, we apply an efficient decision procedure based on the branch-and-bound method. The statistical data of the experiment confirm not only the “scaling window” of MAX-2-SAT discovered by Chayes, Kim and Borgs, but also the recent results of Coppersmith et al. While there is no easy-hard-easy pattern for the complexity of 2-SAT at the phase transition, we show that there is such a pattern for the decision problem of MAX-2-SAT associated with the phase transition. We also identify that the hardest problems are among those with high allowance for false clauses but low number of clauses.
For the entire collection see [Zbl 1109.68315].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI
[1] D. Achlioptas and G. B. Sorkin, Optimal myopic algorithms for 3-SAT, 41st Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA 2001, pp. 590-600.
[2] J. Alber, J. Gramm, R. Niedermeier, Faster exact algorithms for hard problems: A parameterized point of view. Preprint, submitted to Elsevier, August, 2000 · Zbl 0973.68256
[3] S. Arora, C. Lund. Hardness of approximation. In D. Hochbaum (ed.): Approximation algorithms for NP-hard problems, Chapter 10, pages 399-446.
[4] N. Bansal, V. Raman, Upper bounds for MaxSat: Further improved. In Aggarwal and Rangan (eds.): Proceedings of 10th Annual conference on Algorithms and Computation, ISSAC’99, volume \bf1741 of Lecture Notes in Computer Science, pages 247-258, Springer-Verlag, 1999. · Zbl 0971.68069
[5] Bollobas, B.; Borgs, C.; Chayes, J.T.; Kim, J.H.; Wilson, D.B., The scaling window of the 2-SAT transition, Random structures and algorithms, 18, no 3, 201-256, (2001) · Zbl 0979.68053
[6] Borchers, B.; Furman, J., A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems, Journal of combinatorial optimization, 2, 4, 299-306, (1999) · Zbl 0954.90026
[7] A. Z. Broder, A. M. Frieze, E. Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX 1993, ACM Press, 1993, pp. 322-330. · Zbl 0801.68082
[8] V. Chvatal, B. Reed, Mick gets some (the odds are on his side), 33th Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992. IEEE Comput. Soc. Press, 1992, pp. 620-627. · Zbl 0977.68538
[9] D. Coppersmith, D. Gamarnik, M. Hajiaghay, G. B. Sorkin. Random MAX SAT, random MAX CUT, and their phase transitions. Proceedings of Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 12-14, 2003, Baltimore, MD. · Zbl 1094.68573
[10] E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning. A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search. Theoretical Computer Science> 2002. · Zbl 1061.68071
[11] Goerdt, A., A threshold for unsatisfiability, J. comput. system sci, 53, no. 3, 469-486, (1996) · Zbl 0870.68077
[12] J. Gramm, E. A. Hirsch, R. Niedermeier, P. Rossmanith: New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT. Preprint, submitted to Elsevier, May, 2001. · Zbl 1051.68078
[13] Hansen, P.; Jaumard, B., Algorithms for the maximum satisfiability problem, Computing, 44, 279-303, (1990) · Zbl 0716.68077
[14] E. A. Hirsch. A new algorithm for MAX-2-SAT. In Proceedings of 17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000, vol. 1770, Lecture Notes in Computer Science, pages 65-73. Springer-Verlag. · Zbl 0959.68047
[15] Hirsch, E.A., New worst-case upper bounds for SAT, Journal of automated reasoning, 24, 4, 397-420, (2000) · Zbl 0960.03009
[16] Janson, S.; Stamatiou, Y.C.; Vamvakari, M., Bounding the unsatisfiability threshold of random 3-SAT, Random structures and algorithms, 17, no. 2, 103-116, (2000) · Zbl 0958.03028
[17] Mahajan, M.; Raman, V., Parameterizing above guaranteed values: maxsat and maxcut, Journal of algorithms, 31, 335-354, (1999) · Zbl 0921.68052
[18] R. Niedermeier, Some prospects for efficient fixed parameter algorithms. In Proc. of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM ’98), Springer, LNCS 1521, pages 168-185, November, 1998.
[19] Niedermeier, R.; Rossmanith, P., New upper bounds for maximum satisfiability, Journal of algorithms, 36, 63-88, (2000) · Zbl 0959.68049
[20] H. Zhang, H. Shen, New exact algorithms for MAX-2-SAT. Submitted to International Workshop on First-order Theorem Proving (FTP 2003). · Zbl 1261.68073
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.