Parallelization of local search for Euclidean Steiner tree problem

ABSTRACT

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a given fixed points in the plane, allowing the addition of auxiliary points known as Steiner points. Parallel implementations of local search algorithm are an effective technique to speed up the search for a solution of Steiner tree problem. This technique not only allows to solve larger Steiner tree problem or to find improved solutions with respect to their sequential counterparts, but also it leads to further robustness in the algorithm. In this paper, we concentrate on the problem of finding a Euclidean Steiner tree using parallel local search technique. The main contribution of this work is the O(n² log² n+log n log(n/log n)) parallel local search algorithm for computing Steiner tree on the Euclidean plane. The main advantage of the algorithm is that it does not need synchronization. As a result, it has no communication overhead.

REFERENCES

• 1: Emile Aarts , Jan K. Lenstra, Local Search in Combinatorial Optimization, John Wiley & Sons, Inc., New York, NY, 1997
• 2: T. A. Feo and M. G. C. Resende. A probabilistic heuristic for computationally difficult set covering problem. Operations Research Letters, (8):67--71, 1989.
• 3: T. A. Feo and M. G. C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, (6):109--133, 1995.
• 4: S. L. Martins , M. G. C. Resende , C. C. Ribeiro , P. M. Pardalos, A Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy, Journal of Global Optimization, v.17 n.1-4, p.267-283, September 2000 [doi>10.1023/A:1026546708757]
• 5: Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X]
• 6: Simone L. Martins , Celso C. Ribeiro , Mauricio C. Souza, A Parallel GRASP for the Steiner Problem in Graphs, Proceedings of the 5th International Symposium on Solving Irregularly Structured Problems in Parallel, p.285-297, August 09-11, 1998
• 7: S. A. Canuto. Local search for the prize-Collecting Steiner tee problem. M.Sc. Dissertation, Department of Computer Science, Catholic University of Rio de Janeiro, 2000.
• 8: S. A. Canuto, M. G. C. Resende, and C. C. Ribeiro. Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks, (38):50--58, 2001.
• 9: Y. Handa, H. Ono, K. Sadakane, and M. Yamashita. Neighborhood composition: A parallelization of local search algorithms. Lecture Notes in Computer Science, Vol.3241:155--163, Springer-Verlag, Berlin Heidelberg, 2004.
• 10: M. Zachariasen and P. Winter. Concatenation-based greedy heuristics for the Steiner tree problem in the Euclidean plane. Algorithmica, (25):418--437, 1999.
• 11: D. T. Lee. On k-nearest neighbor Voronoi Diagrams in the plane. IEEE Transactions on Computers, C-31(6):478--487, 1982.
• 12: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 13: F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem, Annals of Discrete Mathematics. North-Holland, Amsterdam, 1992.
• 14: M. Zachariasen and P. Winter. Concatenation-based greedy heuristics for the Steiner tree problem in the Euclidean plane. Technical Report 97/20, DIKU, Department of Computer Science, University of Copenhagen, 1997.
• 15: Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
• 16: D. T. Lotarev , A. V. Suprun , A. P. Uzdemir, Local Optimization in the Steiner Problem on the Euclidean Plane, Automation and Remote Control, v.65 n.7, p.1089-1098, July 2004 [doi>10.1023/B:AURC.0000038715.76668.83]
• 17: E. Cantu-Paz. Implementing fast and flexible parallel genetic algorithms. In: Chambers, L. D. (ed.): Practical Handbook of Genetic Algorithms, vol III, 65--84, CRC Press, 1999.
• 18: F. Fernandez, J. M. Sanchez, M. Tomassini, and J. A. Gomez. A parallel genetic programming tool based on PVM. Lecture Notes in Computer Science, (1697):241--248, Springer-Verlag, Berlin Heidelberg, 1999.
• 19: Luiz S. Ochi , Dalessandro S. Vianna , Lúcia M. A. Drummond , André O. Victor, A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet, Future Generation Computer Systems, v.14 n.5-6, p.285-292, Dec. 1998 [doi>10.1016/S0167-739X(98)00034-X]
• 20: S. C. Porto and C. C. Ribeiro. A case study on parallel synchronous implementations of tabu search based on neighborhood decomposition. Investigacion Operativa, (5):233--259, 1996.
• 21: Stella C.S. Porto , João Paulo F.W. Kitajima , Celso C. Ribeiro, Performance evaluation of a parallel tabu search task scheduling algorithm, Parallel Computing, v.26 n.1, p.73-90, Jan. 2000 [doi>10.1016/S0167-8191(99)00096-4]
• 22: E. G. Talbi , Z. Hafidi , J.-M. Geib, A parallel adaptive tabu search approach, Parallel Computing, v.24 n.14, p.2003-2019, Dec. 1998 [doi>10.1016/S0167-8191(98)00086-6]
• 23: E.-G. Talbi, Z. Hafidi, and J.-M. Geib. Parallel adaptive tabu search for large optimization problems. Metaheuristics: Advances and Trends. In: S. Voss, S. Martello, I. H. Osma, and C. Roucairol, (eds.): Local Search Paradigms for Optimization, 255--266, Kluwer, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Theory

Keywords:
Steiner tree, local search, parallel algorithm, proximity structure