Title: Hybrid algorithms for 3-SAT optimisation using MapReduce on clouds

Authors: Marcos Barreto; Sergio Nesmachnow; Andrei Tchernykh

Addresses: Universidad de la República, Herrera y Reissig 565, Montevideo, 11300, Uruguay ' Universidad de la República, Herrera y Reissig 565, Montevideo, 11300, Uruguay ' CICESE Research Center, Carretera Ensenada-Tijuana 3918, Zona Playitas, Ensenada, 22860, Mexico

Abstract: This article presents the advances on applying a MapReduce approach for solving optimisation problems using Hadoop on cloud computing systems. The main advantages and limitations of the proposed strategy are presented and commented. A concrete case study is reported, analysing several algorithmic approaches to solve the 3-SAT, a well-known version of the Boolean satisfiability problem. Several variants of the MapReduce 3-SAT solver are designed and evaluated to demonstrate that the collaborative approach is a promising option for solving optimisation problems in the cloud.

Keywords: MapReduce; Hadoop; optimisation; cloud; 3-SAT.

DOI: 10.1504/IJICA.2018.090835

International Journal of Innovative Computing and Applications, 2018 Vol.9 No.1, pp.44 - 64

Received: 22 Apr 2017
Accepted: 12 Sep 2017
Published online: 28 Mar 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article