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. 217226.
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 maxMat of any maximum matching is a lower bound for the length minStSt 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 minStSt/maxMat 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 minSt/minStSt and minSt/maxMat. We give tight upper bounds for the case where distances are measured according to the Manhattan metric: We show that in threedimensional space, minStSt/maxMat is bounded by 3/2, while in twodimensional space minStSt=maxMat, extending some independent observations by Tamir and Mitchell. Finally, we show that minSt/minStSt has a tight bound of 3/2 in the twodimensional case, and of 5/3 in the threedimensional case.
Download: 
Postscript
 Preprinted Version
Download (250kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  1 (Google Scholar)  
Uncontrolled Keywords:  combinatorial optimization computational complexity connected network Euclidean norm extremal properties geometric inequalities geometric optimization Maximum matching rectilinear norm Weber problem 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr98340 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:46 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/340 