Two-Phase Distributed Algorithm for Solving the Bi-Objective Minimum Spanning Tree Problem: A Preliminary Study

In this paper we present a novel distributed algorithm for solving the Bi-Objective Minimum Spanning Tree (BMST) problem using a two-phase method. The proposed approach leverages the MapReduce computing paradigm to define a distributed version of the most computational intensive part of this method, the second phase. In this phase, a recursive algorithm explores non-supported non-dominated points by evaluating spanning trees within specified regions in the objective space. The distributed nature of our approach allows parallel processing of multiple triangles in the objective space aiming at reducing the execution time and improving the scalability performance. Our preliminary experimental results, conducted using an HPC infrastructure, show that the improvements in the scalability performance when tasks show a balanced processing time are non-negligible but also highlight that a simple distribution of processes among the nodes of the distributed system is not enough to always achieve a good parallelization. Our analysis provided us with useful insights to achieve efficiency and effectiveness of this approach with respect to its sequential counterpart, pointing out its potential for practical applications in multi-objective optimization.