A tighter upper bound for random MAX 2-SAT

Given a conjunctive normal form F with n variables and m =cn 2-clauses, it is interesting to study the maximum number max F of clauses satisfied by all the assignments of the variables (MAX 2-SAT). When c is sufficiently large, the upper bound of f (n, cn) = E(max F) of random MAX 2-SAT had been derived by the first-moment argument. In this paper, we provide a tighter upper bound (3/4)cn + g(c)cn also using the first-moment argument but correcting the error items for f (n.cn), and g(c)= (3/4) cos((1/3) x arccos((4In 2)/c - 1)) - 3/8 when considering the epsilon(3) error item. Furthermore, we extrapolate the region of the validity of the first-moment method is c > 2.4094 by analyzing the higher order error items. (C) 2010 Elsevier B.V. All rights reserved.