skip to main content
10.1145/1185448.1185500acmotherconferencesArticle/Chapter ViewAbstractPublication Pagesacm-seConference Proceedingsconference-collections
Article

Parallelization of local search for Euclidean Steiner tree problem

Published: 10 March 2006 Publication History

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(n2 log2 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]
E. Aarts and J. K. Lenstra. Local Search in Combinatorial Optimization. Princeton University Press, Princeton, New Jersey, (2003).
[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, and P. Pardalos. A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy. Journal of Global Optimization, (17):267--283, 2000.
[5]
K. Mehlhorn. A faster approximation for the Steiner problem in graphs. Information Processing Letters, (27):125--128, 1988.
[6]
S. L. Martins, C. C. Ribeiro, and M. C. Souza. A parallel GRASP for the Steiner problem in graphs. Lecture Notes in Computer Science, Vol.1457:pp.285--297, Springer-Verlag, Berlin Heidelberg, 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]
F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1988.
[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]
C. P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. Theoretical Computer Science, (71):95--132, 1990.
[16]
D. T. Lotarev, A. V. Suprun, and A. P. Uzdemir. Local optimization in the Steiner problem on the Euclidean plane. Automation and Remote Control, 65(7):1089--1098, 2004.
[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]
L. S. Ochi, L. M. Drummond, A. O. Victor, and D. S. Vianna. A parallel Evolutionary algorithm for solving the vehicle routing problem with heterogeneous fleet. Future Generation Computer Systems Journal, 14:285--292, 1998.
[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]
S. C. Porto, J. P. Kitajima, and C. C. Ribeiro. performance evaluation of a parallel tabu search task scheduling algorithm. Parallel Computing, (26):73--90, 2000.
[22]
E.-G. Talbi, Z. Hafidi, and J.-M. Geib. A parallel adaptive tabu search approach. Parallel Computing, (24):2003--2019, 1998.
[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.

Cited By

View all
  • (2015)On the Use of GPU for Accelerating Communication-Aware Mapping TechniquesThe Computer Journal10.1093/comjnl/bxv03759:6(836-847)Online publication date: 29-May-2015
  • (2014)A Survey of Parallel and Distributed Algorithms for the Steiner Tree ProblemInternational Journal of Parallel Programming10.1007/s10766-013-0243-z42:2(287-319)Online publication date: 1-Apr-2014
  • (2008)Transmitting Range Assignments Using Steiner Tree in Ad Hoc Wireless NetworksProceedings of the Fifth International Conference on Information Technology: New Generations10.1109/ITNG.2008.168(408-413)Online publication date: 7-Apr-2008
  • Show More Cited By

Index Terms

  1. Parallelization of local search for Euclidean Steiner tree problem

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    ACMSE '06: Proceedings of the 44th annual ACM Southeast Conference
    March 2006
    823 pages
    ISBN:1595933158
    DOI:10.1145/1185448
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 10 March 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Steiner tree
    2. local search
    3. parallel algorithm
    4. proximity structure

    Qualifiers

    • Article

    Conference

    ACM SE06
    ACM SE06: ACM Southeast Regional Conference
    March 10 - 12, 2006
    Florida, Melbourne

    Acceptance Rates

    ACMSE '06 Paper Acceptance Rate 100 of 244 submissions, 41%;
    Overall Acceptance Rate 502 of 1,023 submissions, 49%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 17 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2015)On the Use of GPU for Accelerating Communication-Aware Mapping TechniquesThe Computer Journal10.1093/comjnl/bxv03759:6(836-847)Online publication date: 29-May-2015
    • (2014)A Survey of Parallel and Distributed Algorithms for the Steiner Tree ProblemInternational Journal of Parallel Programming10.1007/s10766-013-0243-z42:2(287-319)Online publication date: 1-Apr-2014
    • (2008)Transmitting Range Assignments Using Steiner Tree in Ad Hoc Wireless NetworksProceedings of the Fifth International Conference on Information Technology: New Generations10.1109/ITNG.2008.168(408-413)Online publication date: 7-Apr-2008
    • (2008)A Parallel Steiner Tree Construction on the Server-Client Model of ComputationProceedings of the Fifth International Conference on Information Technology: New Generations10.1109/ITNG.2008.167(1281-1283)Online publication date: 7-Apr-2008
    • (2008)Execution Time Analysis of a Parallel Steiner Tree Algorithm on Server-Client Model of ComputationProceedings of the Seventh IEEE/ACIS International Conference on Computer and Information Science (icis 2008)10.1109/ICIS.2008.91(415-420)Online publication date: 14-May-2008
    • (2006)A Parallel Local Search Algorithm for Euclidean Steiner Tree ProblemProceedings of the Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing10.1109/SNPD-SAWN.2006.7(157-164)Online publication date: 19-Jun-2006

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media