Anna Schulze
Zentrum für Angewandte Informatik Köln
Universität zu Köln

2-Approximation für Manhattan Netzwerke

Es wird eine 2-Approximation für Manhattan-Netzwerke von Chepoi, Nouioua und Vaxes vorgestellt ("A rounding algorithm for approximating minimum Manhattan networks"). Der Algorithmus basiert auf einer LP-Relaxierung, bei der das Problem als Fluss-Problem dargestellt wird. Die Lösung des LPs wird gerundet. Dabei werden kombinatorische Strukturen ausgenutzt, die auch von anderen Algorithmen für das Problem verwendet werden.