Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR00-019 | 20th March 2000 00:00

Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search


Authors: Edward Hirsch
Publication: 27th March 2000 16:52
Downloads: 1329


During the past three years there was an explosion of algorithms
solving MAX-SAT and MAX-2-SAT in worst-case time of the order
c^K, where c<2 is a constant, and K is the number of clauses
in the input formula. Such bounds w.r.t. the number of variables
instead of the number of clauses are not known.

Also, it was proved that approximate solutions for these problems
(even beyond inapproximability ratios) can be obtained faster
than exact solutions. However, the corresponding exponents still
depended on the number of clauses in the input formula.
In this paper we give a randomized (1-\epsilon)-approximation
algorithm for MAX-k-SAT. This algorithm runs in time of the order
c_{k,\epsilon}^N, where N is the number of variables,
and c_{k,\epsilon}<2 is a constant depending on k and \epsilon.

ISSN 1433-8092 | Imprint