zbMATH — the first resource for mathematics

Random MAX SAT, random MAX CUT, and their phase transitions. (English) Zbl 1077.68118
Summary: With random inputs, certain decision problems undergo a phase transition. We prove similar behavior in an optimization context. Given a conjunctive normal form (CNF) formula $$F$$ on $$n$$ variables and with $$m$$ $$k$$-variable clauses, denote by max $$F$$ the maximum number of clauses satisfiable by a single assignment of the variables. (Thus the decision problem $$k$$-SAT is to determine ifmax $$F$$ is equal to $$m$$.) With the formula $$F$$ chosen at random, the expectation of max $$F$$ is trivially bounded by $$(3/4)m \leqslant \mathbb E \max F \leqslant m$$. We prove that for random formulas with $$m = \lfloor cn \rfloor$$ clauses: for constants $$c < 1$$, $$\mathbb E \max F$$ is $$\lfloor cn \rfloor - \Theta (1/n)$$; for large $$c$$, it approaches $$((3/4)c + \Theta (\sqrt c))n$$; and in the window $$c = 1 + \Theta (n^{-1/3})$$, it is $$cn - \Theta (1)$$. Our full results are more detailed, but this already shows that the optimization problem MAX 2-SAT undergoes a phase transition just as the 2-SAT decision problem does, and at the same critical value $$c = 1$$. Most of our resultsare established without reference to the analogous propositions for decision 2-SAT, and can be used to reproduce them.
We consider online versions of MAX 2-SAT, and show that for one version the obvious greedy algorithm is optimal; all other natural questions remain open. We can extend only our simplest MAX 2-SAT results to MAX $$k$$-SAT, but we conjecture a MAX $$k$$-SAT limiting function conjecture analogous to the folklore satisfiability threshold conjecture, but open even for $$k = 2$$. Neither conjecture immediately implies the other, but it is natural to further conjecture a connection between them. We also prove analogous results for random MAX CUT.

MSC:
 68W20 Randomized algorithms 68Q25 Analysis of algorithms and problem complexity
Full Text:
References:
 [1] and The asymptotic order of the k-SAT threshold, Proc 43rd Annu IEEE Symp Found Comput Sci, 2002, pp. 779-788. [2] and The threshold for random k-SAT is 2k(ln 2 + o(1)), Proc 35th Annu ACM Symp Theory Computing, 2003, pp. 223-231. · Zbl 1192.68333 [3] and Optimal myopic algorithms for random 3-SAT, 41st Annu Symp Found Comput Sci, IEEE Comput Soc Press, Los Alamitos, CA, 2000, pp. 590-600. [4] and On the maximum satisfiability of random formulas, Proc 44th Symp Found Comput Sci (FOCS 2003), IEEE Computer Society, October 2003, pp. 362-370. [5] Aldous, Probab Theory Related Fields 93 pp 507– (1992) [6] Aldous, Random Structures Algorithms 18 pp 381– (2001) [7] and The objective method: Probabilistic combinatorial optimization and local weak convergence, preprint, 2002. [8] and An upper bound for the maximum cut mean value, Graph-Theoretic Concepts in Computer Science, Berlin, 1997, Lecture Notes in Computer Science 1335, Springer-Verlag, Berlin, 1997, pp. 78-84, MR 99d:68185. [9] Bohman, Random Structures Algorithms 19 pp 75– (2001) [10] and Avoiding a giant component II, unpublished manuscript, February 2002. [11] ? Martingales, isoperimetric inequalities and random graphs,? Combinatorics, Eds. and Colloq Math Soc János Bolyai, No. 52, North Holland, Amsterdam, 1988, pp. 113-139. [12] Modern graph theory, Springer-Verlag, New York, 1998. · Zbl 0902.05016 · doi:10.1007/978-1-4612-0619-4 [13] Bollobás, Random Structures Algorithms 18 pp 201– (2001) [14] and On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proc Fourth Annu ACM-SIAM Symp Discrete Algorithms, Austin, TX, 1993, ACM, New York, 1993, pp. 322-330, MR 94b:03023. [15] and Mick gets some (the odds are on his side), 33th Annu Symp Found Comput Sci, Pittsburgh, PA, IEEE Comput Soc Press, Los Alamitos, CA, 1992, pp. 620-627. · Zbl 0977.68538 [16] and MAX k-CUT and approximating the chromatic number of random graphs, Proc Thirtieth Int Coll Automata, Languages, Programming, Lecture Notes in Computer Science 2719, Springer, 2003, pp. 200-211. · Zbl 1039.68167 [17] and Random MAX SAT, random MAX CUT, and their phase transitions, Proc 14th Annu ACM-SIAM Symp Discrete Algorithms, Baltimore, MD, 2003, ACM, New York, January 2003, pp. 364-373. [18] Creignou, Discrete Appl Math 96/97 pp 41– (1999) [19] Creignou, Theor Inform Appl 37 pp 127– (2003) [20] Creignou, Combin Probab Comput 12 pp 113– (2003) [21] Díaz, Theoret Comput Sci 307 pp 531– (2003) [22] Dubois, C R Math Acad Sci Paris 335 pp 963– (2002) · Zbl 1038.68052 · doi:10.1016/S1631-073X(02)02563-3 [23] and Typical random 3-SAT formulae and the satisfiability threshold, 11th Annu ACM-SIAM Symp Discrete Alg, San Francisco, CA, 2000, ACM, New York, 2000, pp. 126-127. [24] and Typical random 3-SAT formulae and the satisfiability threshold, Tech Report TR03-007, Electronic Colloquium on Computational Complexity, 2003, http://www.eccc.uni-trier.de/eccc-reports/2003/TR03-007/index.html. [25] Probability: Theory and examples, 2nd edition, Duxbury Press, Belmont, CA, 1996, MR 98m:60001. [26] On random 2-SAT, manuscript, 1992. [27] Fernandez de la Vega, Theoret Comput Sci 265 pp 131– (2001) [28] Friedgut, J Amer Math Soc 12 pp 1017– (1999) [29] A proof of Alon’s second eigenvalue conjecture, unpublished manuscript, http://www.math.ubc.ca/jf/pubs/, 2002. [30] and On the second eigenvalue in random regular graphs, 21st Annu ACM Symp Theory Computing, ACM Press, Seattle, WA, 1989, pp. 587-598. [31] Gamarnik, Probab Theory Related Fields pp 104– (2004) [32] Goemans, J ACM 42 pp 1115– (1995) [33] Goerdt, J Comput System Sci 53 pp 469– (1996) [34] Some optimal inapproximability results, STOC ’97 El Paso, TX, ACM, New York, 1997, pp. 1-10 (electronic), MR 1 715 618. [35] and Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000, MR 2001k:05180. · doi:10.1002/9781118032718 [36] Janson, Random Structures Algorithms 17 pp 103– (2000) [37] and Max Cut on sparse random graphs, unpublished manuscript, September 2002. [38] and The probabilistic analysis of a greedy satisfiability algorithm, Fifth Int Symp Theory Appl Satisfiability Testing, 2002, pp. 362-376. [39] and A 7/8-approximation algorithm for MAX 3SAT?, Proc 38th Annu IEEE Symp Found Comput Sci, Miami Beach, FL, IEEE Press, New York, 1997, pp. 406-415. [40] Poisson cloning model for random graphs, in preparation. [41] and Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems, Proc IPCO, 2002, pp. 67-82. · Zbl 1049.90535 [42] On the method of bounded differences, London Mathematical Society Lecture Note Series, Vol. 141, Cambridge University Press, Cambridge, 1989, pp. 148-188. [43] Discrete-parameter martingales, revised edition, North-Holland, Amsterdam, 1975, translated from the French by T. P. Speed, North-Holland Mathematical Library, Vol. 10, MR 53 #6729. [44] Ten lectures on the probabilistic method, 2nd edition, SIAM, Philadelphia, 1994. · Zbl 0822.05060 · doi:10.1137/1.9781611970074 [45] Trevisan, SIAM J Comput 29 pp 2074– (2000) [46] Verhoeven, Inform Process Lett 72 pp 119– (1999) [47] The bisection of random graphs: Rigorous bounds using the analysis of algorithms, unpublished manuscript, http://ycverhoeven.free.fr/index.en.html, 2000. [48] Quelques utilisations des arbres en combinatoire, Ph.D. thesis, Université Paris-Sud, 2001. [49] Wilson, Random Structures Algorithms 21 pp 182– (2002) [50] Wormald, Ann Appl Probab 5 pp 1217– (1995)
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.