We propose a simple and deterministic algorithm for solving MAX2SAT, which runs O(n(n+m)) time where n and m are respectively the number of variables and clauses.
For discussing it average case performance, we propose one natural ``planted solution model''; a way to generate a MAX2SAT instance under a certain distribution defined by parameters p and r.
We first show that
if p = Omega((ln^2 n)/n) and p >= 9r,
then with high probability
the planted solutions (there are four planted solutions) are only the optimal solution, unsatisfying 3rn^2 clauses out of (on average) 2pn^2+8rn^2 clauses.
Then under this planted solution model
we show that,
for some constant e > 0,
our algorithm yields one of the planted solutions with high probability if p-r >= n^{-1/2+e}.