![New primal-dual algorithms for Steiner tree problems [An article from: Computers and Operations Research]](https://www.ebooknetworking.net/books/B00/0PC/bigB000PC0QLQ.jpg)
New primal-dual algorithms for Steiner tree problems [An article from: Computers and Operations Research]
Book Details
Author(s)V. Melkonian
PublisherElsevier
ISBN / ASINB000PC0QLQ
ISBN-13978B000PC0QL2
MarketplaceCanada 🇨🇦
Description
This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.
Description:
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 k, where k is the number of terminals, in the case when the problem is restricted to quasi-bipartite graphs. We also give pathologically bad examples for the algorithm performance. To overcome the problems exposed by the bad examples, we design a new framework for primal-dual algorithms which can be applied to all of our problems. The main feature of the new approach is that, unlike the traditional primal-dual algorithms, it keeps the dual solution in the interior of the dual feasible region. The new approach allows us to avoid including too many arcs in the solution, and thus achieves a smaller-cost solution. Our computational results show that the interior-point version of the primal-dual most of the time performs better than the original primal-dual method.
Description:
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 k, where k is the number of terminals, in the case when the problem is restricted to quasi-bipartite graphs. We also give pathologically bad examples for the algorithm performance. To overcome the problems exposed by the bad examples, we design a new framework for primal-dual algorithms which can be applied to all of our problems. The main feature of the new approach is that, unlike the traditional primal-dual algorithms, it keeps the dual solution in the interior of the dual feasible region. The new approach allows us to avoid including too many arcs in the solution, and thus achieves a smaller-cost solution. Our computational results show that the interior-point version of the primal-dual most of the time performs better than the original primal-dual method.
