The Local Search algorithm is one of the simplest heuristic algothms for solving the MAX-SAT problem. The goal of this paper is to estimate the relative error produced by this algorithm being applied to random 3-CNFs with fixed density e. We prove that, for any e, there is a constant c such that a weakened version of Local Search that we call One-Pass Local Search almost surely outputs an assignment containing cn + o(n) unsatisfied clauses. Then using a certain assumtion we also show this for Local Search. Although the assumption remains unproved the results well matches experiments.
展开▼
