# On Minimum Stars, Minimum Steiner Stars, and Maximum Matchings

Fekete, Sandor P. and Meijer, Henk (1999) On Minimum Stars, Minimum Steiner Stars, and Maximum Matchings.
Published In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry : SCG '99 ; June 13- 16, 1999, Miami Beach, Florida ACM 1999, pp. 217-226.

## Abstract

We discuss properties and values of maximum matchings and minimum median problems for finite point sets. In particular, we consider ''minimum stars'', which are defined by a center chosen from the given point set, such that the total geometric distance |St| 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 point), we get a ''minimum Steiner star'', of total length |StSt|. As a consequence of triangle inequality, the total length max|Mat| of any maximum matching is a lower bound for the length min|StSt| of a minimum Steiner star, which makes this ratio 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 min|StSt|/max|Mat| cannot exceed 2/sqrt{3}. 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 min|St|/min|StSt| and min|St|/max|Mat|. 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|StSt|/max|Mat| is bounded by 3/2, while in two-dimensional space min|StSt|=max|Mat|, extending some independent observations by Tamir and Mitchell. Finally, we show that min|St|/min|StSt| has a tight bound of 3/2 in the two-dimensional case, and of 5/3 in the three-dimensional case.

Actions:
Download: Postscript - Preprinted Version Download (250kB) | Preview View Item (Login required)
Content information:
Item Type: Proceedings article 1 (Google Scholar) | combinatorial optimization computational complexity connected network Euclidean norm extremal properties geometric inequalities geometric optimization Maximum matching rectilinear norm Weber problem 51-XX Geometry > 51Mxx Real and complex geometry > 51M16 Inequalities and extremum problems 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization Mathematical Institute Digital Object Identifier (DOI)
Deposit Information:
ZAIK Number: zpr98-340 Archive Admin 02 Apr 2001 00:00 19 Dec 2011 09:46 http://e-archive.informatik.uni-koeln.de/id/eprint/340