Universität zu Köln

Schulze, Anna (2008). Approximation Algorithms for Network Design Problems. PhD thesis, Universität zu Köln.

Preview

PDF AnnaSchulze.pdf Download (1MB)

Abstract

We consider different variants of network design problems. Given a set of points in the plane we search for a shortest interconnection of them. In this general formulation the problem is known as Steiner tree problem. We consider the special case of octilinear Steiner trees in the presence of hard and soft obstacles. In an octilinear Steiner tree the line segments connecting the points are allowed to run either in horizontal, vertical or diagonal direction. An obstacle is a connected region in the plane bounded by a simple polygon. No line segment of an octilinear Steiner tree is allowed to lie in the interior of a hard obstacle. If we intersect a Steiner tree with the interior of a soft obstacle, no connected component of the induced subtree is allowed to be longer than a given fixed length. We provide polynomial time approximation schemes for the octilinear Steiner tree problem in the presence of hard and soft obstacles. These were the first presented approximation schemes introduced for the problems. Additionally, we introduce a (2+epsilon)-approximation algorithm for soft obstacles. We then turn to Euclidean group Steiner trees. Instead of a set of fixed points we get for each point a set of potential locations (combined into groups) and we need to pick only one location of each group. The groups we consider lie inside disjoint regions fulfilling a special property so-called alpha-fatness. Roughly speaking, the term alpha-fat specifies the shape of the region in comparison to a disk. We give the first approximation algorithm for this problem and achieve an approximation ratio of (1+epsilon)(9.093alpha +1). Last, we consider Manhattan networks. They are allowed to contain edges only in horizontal and vertical direction. In contrast to Steiner trees they contain a shortest path between each pair of points. We introduce insights into the structure of Manhattan networks, particularly in the context of so-called staircases. We give three new approximation algorithms for the Manhattan network problem, the first with approximation ratio 3 and two algorithms with ratio 2. To this end we introduce two algorithms for the Manhattan network problem of staircases. The first algorithm solves the problem to optimality the second yields a 2-approximation. Variants of both algorithms are already known in the literature. Since we use a slightly different definition of staircases and we need special properties of them, we adopt the algorithms to our situation. The 2-approximation algorithms achieve the best known approximation ratio of an algorithm for the Manhattan network problem known so far. Last we give an idea how we could possibly find an algorithm with better approximation ratio.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Approximationsalgorithmen für Netzwerkdesignprobleme German
Translated abstract:	Abstract Language Diese Arbeit beschäftigt sich mit Netzwerkdesign-Problemen. Gegeben ist eine Menge von Punkten in der Ebene. Gesucht wird nach einer Menge von Kanten mit minimaler Gesamtlänge, die alle Punkte miteinander verbindet. In dieser allgemeinen Formulierung ist das Problem als Steinerbaum-Problem bekannt. Wir betrachten in dieser Arbeit oktilineare Steinerbäume mit harten und weichen Blockaden. Ein oktilinearer Steinerbaum darf Kanten enthalten, die in horizontaler, vertikaler oder diagonaler Richtung verlaufen. Eine Blockade ist eine zusammenhängende Region in der Ebene, die durch ein einfaches Polygon berandet wird. Keine Kante eines oktilinearen Steinerbaums darf im Inneren einer harten Blockade liegen. Wenn wir einen Steinerbaum mit dem Inneren einer weichen Blockade schneiden, dann darf keine der sich daraus ergebenden Zusammenhangskomponenten länger als eine vorgegebene Länge sein. Wir führen polynomielle Approximationsschemata für das oktilineare Steinerbaum-Problem mit harten und weichen Blockaden ein. Für diese Probleme waren dies die ers\-ten vorgestellten Approximationsschemata. Zusätzlich geben wir noch einen 2-Approximationsalgorithmus für das Problem mit weichen Blockaden an. Danach beschäftigen wir uns mit euklidischen Gruppensteinerbäumen. Hierbei hat man anstatt einer festen Menge von Punkten für jeden Punkt eine Menge von möglichen Positionen. Diese möglichen Positionen werden zu Gruppen zusammengefasst. Wir betrachten den Fall, dass die Gruppen innerhalb disjunkter Regionen liegen, die alle die spezielle Eigenschaft der sogenannten alpha-Dicke erfüllen. Grob gesagt spezifiziert der Begriff alpha-Dicke die Form einer Region im Vergleich zum Kreis. Wir führen den ersten Approximationsalgorithmus für dieses Problem ein und erreichen eine Approximationsgüte von (1+epsilon)(9.093alpha +1). Als letztes betrachten wir Manhattan-Netzwerke. Sie dürfen Kanten enthalten, die in horizontaler und vertikaler Richtung verlaufen. Im Vergleich zu Steinerbäumen enthalten sie zusätzlich einen kürzesten Weg zwischen je zwei Punkten. Wir führen drei neue Approximationsalgorithmen für das Manhattan-Netzwerk-Problem ein, den ersten mit Approximationsgüute 3 und zwei Algorithmen mit Güte 2. Für diese Algorithmen benötigen wir Algorithmen, die das Manhattan-Netzwerk-Problem für Treppen lösen. Wir geben zwei Algorithmen für dieses spezielle Problem an. Der erste löst Manhattan-Netzwerke für Treppen optimal, der zweite erreicht eine Approximationsgüte von 2. Ähnliche Ansätze wurden vorher schon diskutiert. Da wir eine etwas andere Definition von Treppen benutzen und wir zusätzlich spezielle Eigenschaften brauchen, die unsere Treppen erfüllen, haben wir diese Ansätze auf unseren Fall übertragen. Die 2-Approximationsalgorithmen für allgemeine Manhattan-Netzwerke erreichen die bisher beste bekannte Approximationsgüte. German
Creators:	Creators Email ORCID ORCID Put Code Schulze, Anna schulze@zpr.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-25195
Date:	2008
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects:	Mathematics
Uncontrolled Keywords:	Keywords Language Approximationsalgorithmen, Steinerbäume, Manhattannetzwerke German approximation algorithms, Steiner trees, Manhattan networks English
Date of oral exam:	16 October 2008
Referee:	Name Academic Title Schrader, Rainer Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/2519