A decentralized load balancing strategy for parallel search-three optimization. (c2010)

Abstract

Current generation supercomputers have thousands of cores awaiting highly demanding computations and applications. One area that could largely benefit from such processing capabilities is clearly that of exact algorithms for NP-hard problems. The interest in exact algorithms is more than fifty years old, but seems to have gained great momentum recently with the emergence of parameterized complexity and new exact algorithmic techniques. Moreover, given the proved limitation of polynomial-time approximation algorithms, many research fields witness greater need for accurate computations. Motivated by the above facts, we propose a general implementation framework that targets parallel exact algorithms for NP-hard graph problems. In addition to efficiency, we tackle the problem of scalability by combining a decentralized dynamic load balancing strategy with new coding techniques for exact graph algorithms. As a case-study, we use our framework to implement parallel algorithms for the Vertex Cover and Dominating Set problems. We present experimental results that show notable improved running times and high scalability on all types of input instances.