A tighter upper bound for random MAX \(2\)-SAT
type: Item
instance of: scholarly article
title: A tighter upper bound for random MAX \(2\)-SAT
zbMATH Open document ID: 1260.68164
author: Xuelin Xu
author: Zongsheng Gao
author: Ke Xu
published in: Information Processing Letters
publication date: 2013-04-04T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6150238
zbMATH Keywords: MAX \(2\)-SAT
zbMATH Keywords: upper bound
zbMATH Keywords: first-moment argument
zbMATH Keywords: computational complexity
describes a project that uses: MAX-2-SAT
MaRDI profile type: Publication
full work available at URL: j.ipl.2010.11.002
OpenAlex ID: W2083324225
cites work: Random MAX SAT, random MAX CUT, and their phase transitions
cites work: Some simplified NP-complete graph problems
cites work: Some optimal inapproximability results
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Q4511230
cites work: The scaling window of the 2-SAT transition
cites work: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
cites work: Q4501522
cites work: New worst-case upper bounds for SAT
cites work: New Upper Bounds for Maximum Satisfiability
cites work: An Empirical Study of MAX-2-SAT Phase Transitions
cites work: The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
cites work: Q4954175
DOI: 10.1016/J.IPL.2010.11.002
description: scientific article; zbMATH DE number 6150238