zbMATH — the first resource for mathematics

On the lower bounds of random MAX 3 and 4-SAT. (English) Zbl 07048093
Zhu, Daming (ed.) et al., Frontiers in algorithmics. 10th international workshop, FAW 2016, Qingdao, China, June 30 – July 2, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-39816-7/pbk; 978-3-319-39817-4/ebook). Lecture Notes in Computer Science 9711, 269-278 (2016).
Summary: A \(k\)-CNF formula is said to be \(p\)-satisfiable if there exists a truth assignment satisfying a fraction of \(1-2^{-k}+p2^{-k}\) of its clauses. We obtain better lower bounds for random 3 and 4-SAT to be \(p\)-satisfiable. The technique we use is a delicate weighting scheme of the second moment method, where for every clause we give appropriate weight to truth assignments according to their number of satisfied literal occurrences.
For the entire collection see [Zbl 1407.68047].
68Wxx Algorithms in computer science
Full Text: DOI
[1] Achlioptas, D., Moore, C.: The asymptotic order of the random k-SAT threshold. In: Proceedings of 43rd Annual Symposium on Foundations of Computer Science, pp. 126–127 (2002)
[2] Achlioptas, D., Naor, A., Peres, Y.: On the maximum satisfiability of random formulas. J. Assoc. Comput. Machinary 54(2) (2007) · Zbl 1291.68175
[3] Achlioptas, D., Peres, Y.: The threshold for random \(\(k\)\)-SAT is \(\(2^k\log 2-O(k)\)\). J. Am. Math. Soc. 17(4), 947–973 (2004) · Zbl 1093.68075
[4] Borchers, B., Furman, J.: A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems. J. Comb. Optim. 2(4), 299–306 (1998) · Zbl 0954.90026
[5] Broder, A.Z., Frieze, A.M., Upfal, E.: On the satisfiability and maximum satisfiability of random 3-CNF formulas. In: Proceedings of 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 322–330 (1993) · Zbl 0801.68082
[6] Coppersmith, D., Gamarnik, D., Hajiaghayi, M.T., Sorkin, G.B.: Random MAX 2-SAT and MAX CUT. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD). ACM, New York (2003) · Zbl 1094.68573
[7] de Bruijn, N.G.: Asymptotic Methods in Analysis, 3rd edn. Dover Publications Inc., New York (1981) · Zbl 0556.41021
[8] Fernandez de la Vega, W., Karpinski, M.: \(\(9/8\)\)-approximation algorithm for random max 3-sat. Technical Report TR02-070, Electronic Colloquium on Computational Complexity (2002)
[9] Gao, Z., Liu, J., Xu, K.: A novel weighting scheme for random \(\(k\)\)-SAT. arXiv:1310.4303
[10] Goemans, M., Williamson, D.: New \(\(3/4\)\)-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7, 656–666 (1994) · Zbl 0812.90129
[11] Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001) · Zbl 1127.68405
[12] Hirsch, E.A.: A new algorithm for MAX-2-SAT. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, p. 65. Springer, Heidelberg (2000) · Zbl 0959.68047
[13] Vorob’ev, F.Y.: A lower bound for the 4-satisfiability threshold. Discrete Math. Appl. 17(3), 287–294 (2007)
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.