A new approximation algorithm for the Steiner tree problem with performance ratio 5/3

In this paper we present an RNC approximation algorithm for the Steiner tre e problem in graphs with performance ratio 5/3 and RNC approximation algori thms for the Steiner tree problem in networks with performance ratio 5/3 epsilon for all epsilon > 0. This is achieved by considering a related prob lem, the minimum spanning tree problem in weighted 3-uniform hypergraphs. F or that problem we give a fully polynomial randomized approximation scheme. Our approach also gives rise to conceptually much easier and faster (thoug h randomized) sequential approximation algorithms far the Steiner tree prob lem than the currently best known algorithms from Karpinski and Zelikovsky which almost match their approximation factor. (C) 2000 Academic Press.