On Maximum Matchings and Minimum Steiner Stars
Fekete, Sandor P. and Meijer, Henk
(1998)
On Maximum Matchings and Minimum Steiner Stars.
Technical Report
, 11 p.
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 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. We also give results for the case where distances are measured according to the Manhattan metric, extending some observations by Tamir and Mitchell.
Download: 
Postscript
Download (229kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  No citation data. 
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:  zpr98330 

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