[Submitted on 5 May 2020]
Abstract: Randomized Greedy Algorithms (RGAs) are interesting approaches to solve
problems whose structures are not well understood as well as problems in
combinatorial optimization which incorporate the random processes and the
greedy algorithms. This paper introduces a new algorithm that combines the
major features of RGAs and Shortest Path Tree Algorithm (SPTA) to deal with the
Clustered Shortest-Path Tree Problem (CluSPT). In our algorithm, SPTA is used
to determine the shortest path tree in each cluster while the combination
between characteristics of the RGAs and search strategy of SPTA is used to
constructed the edges connecting clusters. To evaluate the performance of the
proposed algorithm, Euclidean benchmarks are selected. The experimental
investigations show the strengths of the proposed algorithm in comparison with
some existing algorithms. We also analyze the influence of the parameters on
the performance of the algorithm.
Submission history
From: Thanh Pham Dinh [view email]
[v1]
Tue, 5 May 2020 08:34:58 UTC (1,181 KB)
