Optimization Techniques for Solving Complex Problems

CHAPTER 11

Divide and Conquer: Advanced Techniques

C. LEÓN, G. MIRANDA, and C. RODRÍGUEZ

Universidad de La Laguna, Spain

11.1 INTRODUCTION

The divide-and-conquer (DnC) technique is a general method used to solve problems. Algorithms based on this technique divide the original problem in to smaller subproblems, solve them, and combine the subsolutions obtained to get a solution to the original problem. The scheme of this technique can be generalized to develop software tools that allow the analysis, design, and implementation of solvers for specific problems. Unfortunately, in many applications it is not possible to find a solution in a reasonable time. Nevertheless, it is possible to increase the size of the problems that can be approached by means of parallel techniques.

There are several implementations of general-purpose schemes using object-oriented paradigms [1–4]. Regarding divide and conquer, we can mention the following: Cilk [5] based on the C language and Satin [6] codified in Java. Satin [7] is a Java framework that allows programmers to easily parallelize applications based on the divide-and-conquer paradigm. The ultimate goal of Satin is to free programmers from the burden of modifying and hand-tuning applications to exploit parallelism. Satin is implemented on top of Ibis [8], a programming environment with the goal of providing an efficient Java-based platform for ...