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 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. We also give results for the case where distances are measured according to the Manhattan metric, extending some observations by Tamir and Mitchell.


Actions:
Download: [img] Postscript
Download (229kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-330
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/330