The maximum 2-satisfiability problem (MAX-2-SAT) is:
given a Boolean formula in $2$-CNF, find a truth
assignment that satisfies the maximum possible number
of its clauses. MAX-2-SAT is MAXSNP-complete.
Recently, this problem received much attention in the
contexts of approximation (polynomial-time) algorithms
and exact (exponential-time) algorithms. In this paper,
we present an exact algorithm solving MAX-2-SAT in time
poly(L) 2^{K/5}, where K is the number of clauses and L
is their total length. Since, in our analysis, we count
only clauses containing exactly two literals, this
bound implies the bound poly(L) 2^{L/10}.

Our results significantly improve previous bounds:
poly(L) 2^{K/2.88} [Niedermeier, Rossmanith, 00] and
poly(L) 2^{K/3.44} (implicit in [Bansal, Raman, 99]).
Concerning the bound w.r.t. L, nothing better than the
bound poly(L) 2^{L/6.89} [Bansal, Raman, 99] for
(general) MAX-SAT was known. Our algorithm, together
with its analysis, is much simpler than recent MAX-SAT
algorithms (previous MAX-2-SAT bounds were obtained by
general MAX-SAT algorithms using inequalities relating
different input formula parameters).

As an application, we derive upper bounds for the
(MAXSNP-complete) maximum cut problem (MAX-CUT), showing
that it can be solved in time poly(M) 2^{M/3}, where M
is the number of edges in the given graph. This is of
special interest for graphs with low vertex degree.