標題: THE SEARCHING OVER SEPARATORS STRATEGY TO SOLVE SOME NP-HARD PROBLEMS IN SUBEXPONENTIAL TIME
作者: HWANG, RZ
CHANG, RC
LEE, RCT
資訊工程學系
Department of Computer Science
關鍵字: COMPUTATIONAL GEOMETRY;NP-HARDNESS
公開日期: 1-四月-1993
摘要: In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts, A(d) and C(d), in such a way that after solving these two subproblems with A(d) and C(d) as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete Euclidean P-median problem (DEPM), the discrete Euclidean P-center problem (DEPC), the Euclidean P-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose O(n(o(square-root P))) algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an O(n(o(square-root n))) algorithm for the ETSP problem, where n is the number of input points.
URI: http://dx.doi.org/10.1007/BF01228511
http://hdl.handle.net/11536/3053
ISSN: 0178-4617
DOI: 10.1007/BF01228511
期刊: ALGORITHMICA
Volume: 9
Issue: 4
起始頁: 398
結束頁: 423
顯示於類別:期刊論文


文件中的檔案:

  1. A1993KT60500005.pdf