Approximation algorithms for Steiner forest: An experimental study. Issue 2 (13th May 2021)

• Record Type: Journal Article
• Authors: Ghalami, Laleh; Grosu, Daniel
• Is Part Of: Networks. Volume 79:Issue 2(2022)
• Page Start: 164
• Page End: 188
• Publication Date: 2021-05-13
• Subjects: approximation algorithms -- performance evaluation -- Steiner forest; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22046
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation algorithms for the Steiner forest, we provide efficient implementations of existing approximation algorithms and conduct a thorough experimental study to characterize their performance. We consider several approximation algorithms: the influential primal‐dual 2‐approximation algorithm due to Agrawal, Klein, and Ravi, the greedy algorithm due to Gupta and Kumar, and a randomized algorithm based on probabilistic approximation by tree metrics. We also consider the simplest heuristic greedy algorithm for the problem, which picks the closest unconnected pair of terminals and connects it using the shortest path between the terminals in the current graph. To characterize the performance of the algorithms, we created a new library with more than one thousand Steiner forest problem instances and conducted an extensive experimental analysis on those instances. Our analysis reveals that for the majority of instances the primal‐dual algorithm is the fastest among all the algorithms considered here, and obtains solutions that are very close to the optimal solutions obtained by solving the integer program formulation of the problem.