Article ID: | iaor20082086 |
Country: | United Kingdom |
Volume: | 34 |
Issue: | 7 |
Start Page Number: | 2147 |
End Page Number: | 2167 |
Publication Date: | Jul 2007 |
Journal: | Computers and Operations Research |
Authors: | Melkonian Vardges |
Keywords: | networks |
We present new primal–dual algorithms for several network design problems. The problems considered are the generalized Steiner tree problem (GST), the directed Steiner tree problem (DST), and the set cover problem (SC) which is a subcase of DST. All our problems are NP-hard; so we are interested in their approximation algorithms. First, we give an algorithm for DST which is based on the traditional approach of designing primal–dual approximation algorithms. We show that the approximation factor of the algorithm is