A Parallel GRASP for MAX-SAT

L. S. Pitsoulis, P. M. Pardalos, and M. G. C. Resende

Lecture Notes in Computer Science, vol. 1180, pp. 575-585, 1996


The weighted maximum satisfiability (MAX-SAT) problem is central in mathematical logic, computing theory, and many industrial applications.  In this paper, we present a parallel greedy randomized adaptive search procedure (GRASP) for solving MAX-SAT problems. Experimental results indicate that almost linear speedup is achieved.

PostScript file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 28 June 2002

Copyright Notice