Abstract
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 andC d, in such a way that after solving these two subproblems withA d andC 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 EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose\(O(n^{o(\sqrt P )} )\) algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an\(O(n^{o(\sqrt n )} )\) algorithm for the ETSP problem, wheren is the number of input points.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aho, A. V., Hopcroft, J. E., and Ullman, J. D.,The Design and Analysis of Computer Algorithms, Bell Telephone Laboratories, Inc., New York, 1976.
Bentley, J. L., Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space, Ph.D. Thesis, Department of Computer Science, University of North Carolina, 1976.
Bentley, J. L., Multidimensional Divide-and-Conquer,Communications of the Association for Computing Machinery, Vol. 23, 1980, pp. 214–229.
Delaunay, B., Sur la sphère vide,Izvestiya Akademii Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, Vol. 7, 1934, pp. 793–800.
Drezner, Z., TheP-Center Problem — Heuristics and Optimal Algorithms,Journal of the Operational Research Society, Vol. 35, No. 8, 1984, pp. 741–748.
Drezner, Z., On the RectangularP-Center Problem,Naval Research Logistics, Vol. 34, 1987, pp. 229–234.
Edelsbrunner, H.,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987.
Held, M., and Karp, R. M., A Dynamic Programming Approach to Sequencing Problems,SIAM Journal on Applied Mathematics, Vol. 10, 1962, pp. 196–210.
Horowitz, E., and Sahni, S.,Fundamentals of Computer Algorithms, Computer Science Press, Rockville, MD, 1978.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B.,The Traveling Salesman Problem — A Guided Tour of Combinatorial Optimization, Wiley-Interscience, New York, 1985.
Lipton, R., and Tarjan, R. E., A Separator Theorem for Planar Graphs,SIAM Journal on Applied Mathematics, Vol. 36, No. 2, 1979, pp. 177–189.
Megiddo, N., Linear-Time Algorithms for Linear Programming inR 3 and Related Problems,SIAM Journal on Computing, Vol. 12, No. 4, 1983, pp. 759–776.
Megiddo, N., and Supowit, K. J., On the Complexity of Some Common Geometric Location Problems,SIAM Journal on Computing, Vol. 13, No. 1, 1984, pp. 182–196.
Mehlhorn, K.,Data Structure and Algorithms 3: Multi-dimensional Search and Computational Geometry, Springer-Verlag, Berlin, 1984.
Miller, G. L., Finding Small Simple Cycle Separators for 2-Connected Planar Graphs,Journal of Computer and System Sciences, Vol. 32, 1986, pp. 265–279.
Nishizeki, T., and Chiba, N.,Planar Graphs, Theory and Algorithms, Elsevier, Amsterdam, 1988.
Papadimitriou, C. H., Some Computational Problems Related to Database Concurrent Control,Proceedings of the Conference on Theoretical Computer Science, University of Waterloo, Waterloo, Ontario, 1977, pp. 275–282.
Papadimitriou, C. H., Worst-Case and Probabilistic Analysis of a Geometric Location Problem,SIAM Journal on Computing, Vol. 10, 1981, pp. 542–557.
Papadimitriou, C. H., and Steiglitz, K., Some Complexity Results for the Traveling Salesman Problem,Proceedings of the 8th Annual ACM Symposium on Theory of Computing, New York, 1976, pp. 1–9.
Preparata, F. P., and Shamos M. I.,Computational Geometry, Springer-Verlag, New York, 1985.
Smith, W. D., Studies in Computational Geometry Motivated by Mesh Generation, accepted byAlgorithmica, 1991.
Voronoi, G., Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier Mémoire: Sur quelques propriétés des formes quadratiques positives parfaites,Journal für die Reine und Angewandte Mathematik, Vol. 133, 1907, pp. 97–178.
Author information
Authors and Affiliations
Additional information
Communicated by C. L. Liu.
This research work was partially supported by the National Science Council of the Republic of China under Grant NSC 79-0408-E007-04.
Rights and permissions
About this article
Cite this article
Hwang, R.Z., Chang, R.C. & Lee, R.C.T. The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica 9, 398–423 (1993). https://doi.org/10.1007/BF01228511
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01228511