Abstract
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.
Invited paper, PARA96 — Workshop on Applied Parallel Computing in Industrial Problems and Optimization, Lyngby, Denmark (August 18–21, 1996)
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G.Y. Ananth, V. Kumar, and P.M. Pardalos. Parallel processing of discrete optimization problems. In Encyclopedia of Microcomputers, volume 13, pages 129–147. Marcel Dekker Inc., New York, 1993.
S.A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third annual ACM Symposium on Theory of Computing, pages 151–158, 1971.
T.A. Feo and M.G.C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133, 1995.
A. Ferreira and P.M. Pardalos, editors. Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques, volume 1054 of Lecture Notes in Computer Science. Springer-Verlag, 1996.
M.R. Garey and D.S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company, New York, 1979.
A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Mancheck, and V. Sunderam. PVM: Parallel Virtual Machine A Users Guide and Tutorial for Networked Parallel Computing. Scientific and Engineering Computation. MIT Press, Massachusetts Institute of Technology, 1994.
J. Gu. Parallel algorithms for satisfiability (SAT) problems. In P.M. Pardalos, M.G.C. Resende, and K.G. Ramakrishnan, editors, Parallel Processing of Discrete Optimization Problems, volume 22 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 105–161. American Mathematical Society, 1995.
D.S. Johnson and M.A. Trick, editors. Cliques, coloring, and Satisfiability; Second DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1996.
P.M. Pardalos, L. Pitsoulis, T. Mavridou, and M.G.C. Resende. Parallel search for combinatorial optimization: Genetic algorithms, simulated annealing and GRASP. Lecture Notes in Computer Science, 980:317–331, 1995.
P.M. Pardalos, L.S. Pitsoulis, and M.G.C. Resende. A parallel GRASP implementation for the quadratic assignment problem. In A. Ferreira and J. Rolim, editors, Parallel Algorithms for Irregularly Structured Problems — Irregular'94, pages 111–130. Kluwer Academic Publishers, 1995.
P.M. Pardalos, M.G.C. Resende, and K.G. Ramakrishnan, editors. Parallel Processing of Discrete Optimization Problems, volume 22 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1995.
M.G.C. Resende and T.A. Feo. A GRASP for Satisfiability. In D.S. Johnson and M.A. Trick, editors, Cliques, coloring, and Satisfiability: Second DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1996.
M.G.C. Resende, L. Pitsoulis, and P.M. Pardalos. Approximate solution of weighted max-sat problems using grasp. In DingZu Du, Jun Gu, and Panos M. Pardalos, editors, Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pardalos, P.M., Pitsoulis, L., Resende, M.G.C. (1996). A parallel GRASP for MAX-SAT problems. In: Waśniewski, J., Dongarra, J., Madsen, K., Olesen, D. (eds) Applied Parallel Computing Industrial Computation and Optimization. PARA 1996. Lecture Notes in Computer Science, vol 1184. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62095-8_62
Download citation
DOI: https://doi.org/10.1007/3-540-62095-8_62
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62095-2
Online ISBN: 978-3-540-49643-4
eBook Packages: Springer Book Archive