Sterne und Matchings

Wenn man für eine gegebene endliche Menge von Punkten ein optimales Zentrum plaziert, das die Summe der Abstände minimiert, so kann man die Verbindungen vom Zentrum zu den Punkten auch als einen speziellen Baum auffassen, einen sogenannten Stern. Ist das Zentrum nicht notwendigerweise ein Punkt der gegebenen Menge, so sprechen wir (in Anlehnung an sogenannte Steinerbäume) von einem Steinerstern. Typischerweise ist man an Sternen und Steinersternen möglichst kleiner Gesamtlänge interessiert.

Ein anderes klassisches Optimierungsproblem für eine Menge von Punkten ist das sogenannte Matching. Hierbei bildet man eine Menge von disjunkten Paaren und addiert die Distanzen der Punkte aller Paare. Es ist nun eine einfache Folge der Dreiecksungleichung, daß die Länge $\min\Vert StSt\Vert$ eines minimalen Steinersternes nicht kürzer sein kann als die Länge $\max\Vert Mat\Vert$eines maximalen Matchings. Für den Fall von Manhattan-Distanzen in der Ebene gilt sogar Gleichheit, für den Fall von euklidischen Distanzen sieht man leicht, daß es Beispiele gibt, für die $\min\Vert StSt\Vert/\max\Vert Mat\Vert>1$ gilt.

Motiviert durch Probleme aus dem Kontext optimaler Kommunikationsnetzwerke hatte Suri bereits 1995 nach dem größtmöglichen Wert dieses Verhältnisses gefragt und wiederholte diese Frage im Juni 1998 als besondere Herausforderung auf der Jahrestagung für algorithmische Geometrie. In Zusammenarbeit mit Prof. Henk Meijer (Queen's University, Kanada) gelang es uns zu beweisen, daß das genannte Verhältnis den Wert $2/\sqrt{3} \approx 1.17$ nicht überschreiten kann, was die bestmögliche Abschätzung ist.

  

Abbildung: Finden eines kleinen Sternes und eines großen Matchings

Darüber hinaus fanden wir eine ganze Reihe von weiteren (zum Teil scharfen) Abschätzungen für die Verhältnisse zwischen minimalen Sternen, minimalen Steinersternen und maximalen Matchings; je nach Metrik und Dimension des Raumes ergeben sich dabei sehr unterschiedliche Werte.