Document Type

Technical Report

Publication Date

1989-05-01

Filename

WUCS-89-15.pdf

DOI:

10.7936/K7MC8XCR

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7MC8XCR

Download

Share

COinS