Document Type
Technical Report
Publication Date
1989-05-01
Technical Report Number
WUCS-89-15
Abstract
In this paper we consider several approximation algorithms for the Steiner tree problem in an attempt to find one whose worst case performance is better than two times optimal. We first examine Rayward-Smith's algorithm to gain insight into why it has worst case performance no better than two. Based on these ideas we propose several new algorithms (approximation schemes). We eliminate from further consideration those which we have bene able to showed have worst case performance that is still no better than two. Then we conjecture that one of these schemes not only has improved worst case performance, but is also the basis for a polynomial scheme. That is, given an e greater than 0 we conjecture that this scheme specifies a polynomial time approximation algorithm with worst case performance within 1 + e times optimal.
Recommended Citation
Waxman, Bernard M., "New Approximation Algorithms for the Steiner Tree Problem" Report Number: WUCS-89-15 (1989). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/728
Comments
Permanent URL: http://dx.doi.org/10.7936/K7MC8XCR