On minimum stars and maximum matchings

We discuss worst-case bounds on the ratio of maximum matching and minimum m edian values for finite point sets. In particular, we consider "minimum sta rs," which are defined by a center chosen from the given point set, such th at the total geometric distance L-S to all the points in the set is minimiz ed. If the center point is not required to be an element of the set (i.e., the center may be a Steiner point), we get a "minimum Steiner star" of tota l length L-SS. As a consequence of triangle inequality, the total length L- M of a maximum matching is a lower bound for the length L-SS of a minimum S teiner star, which makes the worst-case value rho(SS, M) of the value L-SS/ L-M interesting in the context of optimal communication networks, The ratio also appears as the duality gap in an integer programming formulation of a location problem by Tamir and Mitchell. In this paper we show that for a finite set that consists of an even number of points in the plane and Euclidean distances, the worst-case ratio rho(S , M) cannot exceed 2/root 3. This proves a conjecture of Suri, who gave an example where this bound is achieved. For the case of Euclidean distances i n two and three dimensions, we also prove upper and lower bounds for the wo rst-case value rho(S, SS) of the ratio L-S/L-SS, and for the worst-case val ue rho(S, M) of the ratio L-S/L-M. We give tight upper bounds for the case where distances are measured according to the Manhattan metric: we show tha t in three-dimensional space, rho(SS, M) is bounded by 3/2, while in two-di mensional space L-SS = L-M, extending some independent observations by Tami r and Mitchell. Finally, we show that rho(S, SS) is 3/2 in the two-dimensio nal case, and 5/3 in the three-dimensional case.