MAX-2-SAT and MAX-2-CSP are important NP-hard optimization problems generalizing many graph problems. Despite many efforts, the only known algorithm (due to Williams) solving them in less than 2
steps uses exponential space. Scott and Sorkin give an algorithm with
time and polynomial space for these problems, where
is the average variable degree. We improve this bound to
for MAX-2-SAT and
for MAX-2-CSP. We also prove stronger upper bounds for
bounded from below. E.g., for
≥ 10 the bounds improve to
, respectively. As a byproduct we get a simple proof of an
upper bound for MAX-2-CSP, where m is the number of constraints. This matches the best known upper bound w.r.t.
due to Gaspers and Sorkin.