A First Attempt on the Distributed Prize Collecting Steiner Tree Problem
Niccolò G. Rossetti · Skemman · 2015
The goal of this work is to design and simulate a distributed algorithm to solve a novel variant of the Price Collecting Steiner Tree (PCST) problem, where nodes are computing entities with only local information and communication abilities. Our approach is to study existing techniques for the centralized PCST, such as the Primal-Dual Integer Program given by Goemans and Williamson (GW-algorithm), and distributed algorithms for the Minimum Spanning Tree (MST) and minimum Steiner Tree Problem. None of the above adapts easily to our problem. However, we introduce a simple MST-based heuristic that runs on a custom Python simulator. Our heuristic does not guarantee any approximation factor of the optimal solution, but it proved well against benchmark instances found in literature for which it was able to find solutions within the approximation guarantee of the GW-algorithm for all but few instances. We also designed an adaptation of the original GW-algorithm to our distributed model. Though it follows the sequential steps of the original algorithm, this is the first distributed algorithm with an approximation guarantee for the PCST. Simulator and algorithms' code is available on a public repository as free software.