THE K-STEINER RATIO IN THE RECTILINEAR PLANE

A Steiner minimum tree (SMT) in the rectilinear plane is the shortest length tree interconnecting a set of points, called the regular points , possibly using additional vertices. A k-size Steiner minimum tree (k SMT) is one that can be split into components where all regular points are leaves and all components have at most k leaves. The k-Steiner ra tio in the rectilinear plane, Pk, is the infimum of the ratios SMT/kSM T over all finite sets of regular points. The k-Steiner ratio is used to determine the performance ratio of several recent polynomial-time a pproximations for Steiner minimum trees. Previously it was known that in the rectilinear plane, rho(2) = 2/3, rho(3) = 4/5, and (2k - 2)/(2k - 1.) less than or equal to rho(k)(L,(1)) less than or equal to (2k - 1)/(2k) for k greater than or equal to 4. In 1991, P. Berman and V. R amaiyer conjectured that in fact rho(k) = (2k-1)/(2k) for k greater th an or equal to 4. In this paper we prove their conjecture. (C) 1998 Ac ademic Press.