On minimum stars, minimum Steiner stars, and maximum matchings
Sándor P. Fekete, Henk Meijer · 1999
introductionWe discuss properties and values of maximum matchings and minimum median problems for finite point sets.In Dar&&r.we consider "minimum stars".which are defined by a cent& chosen from the given point ' set, such that the total geometric distance min llStl[ to all the points in the set is minimized.If the center point is not required to be an element of the set (i. e., the center may be a Steiner nointj.we net a "minimum Steiner star". of total length -min I[.!?tS'tll."As a consequence of triangle inequality, the total length max IlMatll of any maximum matching is a lower bound for the length min IIStSt() of a minimum Steiner star, which makes the ratio -1 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 an even set of points in the plane and Euclidean distances, the ratio max,,Mat,, min llSt.Stl( ,, ,, cannot exceed 2/& This proves a conjecture of Suri, who gave an example where this bound is achieved.For the case of Euclidean distances in two and three dimensions, we also prove upper and lower bounds for the maximal value of the ratios m and z~,/~~$.We give tight upper bounds for the case where distances are measured according to the Manhattan metric: we show that in three-dimensional space, min ll.StStll max lp4atII 'Parts of this work were done while visiting Queen's University, partially supported by the Deutsche Forschungsgemeinschaft, FE 40713-l.t Parts of this work were done while visiting Universitit zu Kiiln, partially supported by NSERC.Permission to make digital or hard copies ol'all or part of this work for personal or classroom use is granted without fee provided that topics are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citalion on the tirst page.To copy otherwise, Lo