Abstract
In this thesis, we propose a new strategy for designing algorithms, calledthe generalized divide- and- conquer strategy. Suppose that we have aproblem to which the ordinary divide- and- conquer strategy can not beapplied directly. Yet, also suppose that in an optimal solution of thisproblem, there exists a boundary which divides the input points into twoparts, Ad and Cd in such a way that after solving these two subproblemswith Ad and Cd as inputs, respectively, we can merge the respectivesub- solutions into an optimal solution. Let us further assume that thisproblem is an optimization problem. In this case, our generalizeddivide- and conquer strategy will use a boundary generator to generate allpossible boundaries. For each booundary, the problem is solved by theordinary divide- and- coquer strategy. If the boundary generator isguaranteed to generate the desired boundary existing in our optimalsolution, our generalized divide- and- conquer strategy will alwaysproduce an optimal solution. The performance of our approach willcritically depend upon the performance of the boundary generator. It willperform well if the total number of boundaries generated is relativelysmall. We apply this approcah to solve the discrete euclidean P- medianproblem, the Euclidean traveling salesperson problem and the EuclideanP- center problem. For the Euclidean P- median problem and the euclideanP- center problem, we propose（圖表省略）algorithms and for the Euclidean traveling salesperson problem, we proposean（圖表省略）algorithm, where n is the number of input points.