The subject of this thesis is to study approximation algorithms for some network design problems in face of uncertainty. We consider two widely studied models of handling uncertainties - Robust Optimization and Stochastic Optimization. We study a robust version of the well studied Uncapacitated Facility Location Problem (UFLP). In this version, once the set of facilities to be opened is decided, an adversary may close at most β facilities. The clients must then be assigned to the remaining open facilities. The performance of a solution is measured by the worst possible set of facilities that the adversary may close. We introduce a novel LP for the problem, and provide an LP rounding algorithm when all facilities have same opening costs. We also study the 2-stage Stochastic version of the Steiner Tree Problem. In this version, the set of terminals to be covered is not known in advance. Instead, a probability distribution over the possible sets of terminals is known. One is allowed to build a partial solution in the first stage a low cost, and when the exact scenario to be covered becomes known in the second stage, one is allowed to extend the solution by building a recourse network, albeit at higher cost. The aim is to construct a solution of low cost in expectation. We provide an LP rounding algorithm for this problem that beats the current best known LP rounding based approximation algorithm.

The subject of this monograph can be described as the local properties of geometric Steiner minimal trees in finite-dimensional normed spaces. A Steiner minimal tree of a finite set of points is a shortest connected set interconnecting the points. For a quick introduction to this topic and an overview of all the results presented in this work, see Chapter 1. The relevant mathematical background knowledge needed to understand the results and their proofs are collected in Chapter 2. In Chapter 3 we introduce the Fermat-Torricelli problem, which is that of finding a point that minimizes the sum of distances to a finite set of given points. We only develop that part of the theory of Fermat-Torricelli points that is needed in later chapters. Steiner minimal trees in finite-dimensional normed spaces are introduced in Chapter 4, where the local Steiner problem is given an exact formulation. In Chapter 5 we solve the local Steiner problem for all two-dimensional spaces, and generalize this solution to a certain class of higher-dimensional spaces (CL spaces). The twodimensional solution is then applied to many specific norms in Chapter 6. Chapter 7 contains an abstract solution valid in any dimension, based on the subdifferential calculus. This solution is applied to two specific high-dimensional spaces in Chapter 8. In Chapter 9 we introduce an alternative approach to bounding the maximum degree of Steiner minimal trees from above, based on the illumination problem from combinatorial convexity. Finally, in Chapter 10 we consider the related k-Steiner minimal trees, which are shortest Steiner trees in which the number of Steiner points is restricted to be at most k. / Das Thema dieser Habilitationsschrift kann als die lokalen Eigenschaften der geometrischen minimalen Steiner-Bäume in endlich-dimensionalen normierten Räumen beschrieben werden. Ein minimaler Steiner-Baum einer endlichen Punktmenge ist eine kürzeste zusammenhängende Menge die die Punktmenge verbindet. Kapitel 1 enthält eine kurze Einführung zu diesem Thema und einen Überblick über alle Ergebnisse dieser Arbeit. Die entsprechenden mathematischen Vorkenntnisse mit ihren Beweisen, die erforderlich sind die Ergebnisse zu verstehen, erscheinen in Kapitel 2. In Kapitel 3 führen wir das Fermat-Torricelli-Problem ein, das heißt, die Suche nach einem Punkt, der die Summe der Entfernungen der Punkte einer endlichen Punktmenge minimiert. Wir entwickeln nur den Teil der Theorie der Fermat-Torricelli-Punkte, der in späteren Kapiteln benötigt wird. Minimale Steiner-Bäume in endlich-dimensionalen normierten Räumen werden in Kapitel 4 eingeführt, und eine exakte Formulierung wird für das lokale Steiner-Problem gegeben. In Kapitel 5 lösen wir das lokale Steiner-Problem für alle zwei-dimensionalen Räume, und diese Lösung wird für eine bestimmte Klasse von höher-dimensionalen Räumen (den sog. CL-Räumen) verallgemeinert. Die zweidimensionale Lösung wird dann auf mehrere bestimmte Normen in Kapitel 6 angewandt. Kapitel 7 enthält eine abstrakte Lösung die in jeder Dimension gilt, die auf der Analysis von Subdifferentialen basiert. Diese Lösung wird auf zwei bestimmte höher-dimensionale Räume in Kapitel 8 angewandt. In Kapitel 9 führen wir einen alternativen Ansatz zur oberen Schranke des maximalen Grads eines minimalen Steiner-Baums ein, der auf dem Beleuchtungsproblem der kombinatorischen Konvexität basiert ist. Schließlich betrachten wir in Kapitel 10 die verwandten minimalen k-Steiner-Bäume. Diese sind die kürzesten Steiner-Bäume, in denen die Anzahl der Steiner-Punkte auf höchstens k beschränkt wird.

The subject of this thesis is to study approximation algorithms for some network design problems in face of uncertainty. We consider two widely studied models of handling uncertainties - Robust Optimization and Stochastic Optimization. We study a robust version of the well studied Uncapacitated Facility Location Problem (UFLP). In this version, once the set of facilities to be opened is decided, an adversary may close at most β facilities. The clients must then be assigned to the remaining open facilities. The performance of a solution is measured by the worst possible set of facilities that the adversary may close. We introduce a novel LP for the problem, and provide an LP rounding algorithm when all facilities have same opening costs. We also study the 2-stage Stochastic version of the Steiner Tree Problem. In this version, the set of terminals to be covered is not known in advance. Instead, a probability distribution over the possible sets of terminals is known. One is allowed to build a partial solution in the first stage a low cost, and when the exact scenario to be covered becomes known in the second stage, one is allowed to extend the solution by building a recourse network, albeit at higher cost. The aim is to construct a solution of low cost in expectation. We provide an LP rounding algorithm for this problem that beats the current best known LP rounding based approximation algorithm.

[pt] Nesta tese faz-se uma extensa revisão bibliográfica sobre o problema de Steiner na métrica retilínea, destacando-se a aplicação do mesmo no projeto de VLSI. São descritas em detalhes várias heurísticas existentes na literatura para as quais estudam-se a complexidade computacional e a qualidade das soluções obtidas. Além disso, são estabelecidos novos resultados relativos ao comportamento de pior caso destas heurísticas. Propõe-se, ainda, duas novas heurísticas para o problema de Steiner na métrica retilínea para as quais são estudadas a complexidade computacional e a qualidade da solução, inclusive com a análise do pior caso. Uma grande quantidade de testes computacionais permitiu a realização de uma comparação do desempenho das diversas heurísticas implementadas, concluindo-se que uma das novas heurísticas propostas fornece, em média, soluções melhores do que aquelas fornecidas pelas demais heurísticas conhecidas na literatura. / [en] In this dissertation we present a survey about the Steiner problem in the rectilinear metric, illustrating its applications to the VLSI desing. A large number of heurístics already described in literature is studied in details. Moreover, we study the complexity of these heuristics and the quality of their solutions. New results concerning their worst case behavior are stated. We also propose two new heuristics for thew Steiner problem in the rectilinear metric, for which we study the complexity and the quality of the solutions, including the worst case analysis. A large nember of computational experiments was conducted and allowed the comparison of the performances of the heuristics implemented. We conclude from these experiments that, in the average, the solutions obtained by one of the new heuristics are better than the solutions obtained by those alreafy available in the literature.

Neste projeto analisamos jogos de formação de redes que são variantes do problema da floresta de Steiner, nos quais indivíduos desejam conectar conjuntos de vértices terminais em um grafo de forma a minimizar seus custos, podendo dividir o custo das arestas com os demais participantes. Estudamos como o método de divisão de custos influencia na existência e na qualidade dos equilíbrios desses jogos em comparação com o valor da solução ótima centralizada. / In this project we analyze network formation games that are variants of the Steiner forest problem, in which individuals wish to connect sets of terminal vertices of a graph in a way that minimizes their costs, being able to divide the cost of an edge with the other participants. We study how the method used to divide the costs influences the existence and quality of the equilibria of these games in relation to the centralized optimal solution.

Neste projeto estudamos algoritmos de aproximação para o problema da árvore de Steiner com coleta de prêmios. Trata-se de uma generalização do problema da árvore de Steiner, onde é dado um grafo com custos positivos nas arestas e penalidades positivas nos vértices. O objetivo é encontrar uma subárvore do grafo que minimize a soma dos custos das arestas mais a soma das penalidades dos vértices que não pertencem à subárvore. Em 2009, os autores Archer, Bateni, Hajiaghayi e Karloff obtiveram pela primeira vez um algoritmo com fator de aproximação estritamente menor do que 2. Além de analisarmos este algoritmo, estudamos também a implementação de algoritmos 2-aproximação para o problema da árvore de Steiner e da árvore de Steiner com coleta de prêmios. / In this project we analyze approximation algorithms for the prize-collecting Steiner tree problem. This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices. The goal is to find a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don\'t belong to the subtree. In 2009, the authors Archer, Bateni, Hajiaghayi e Karloff described, for the first time an algorithm with approximation factor strictly less than 2. Besides analyzing this algorithm, we also study the implementation of 2-approximation algorithms to the Steiner tree problem and prize-collecting Steiner tree problem.

No description available.

Permission from the author to digitize this work is pending. Please contact the ICS library if you would like to view this work.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Philosophiae Doctor - PhD / A tactical con guration consists of a nite set V of points, a nite set B of blocks and an incidence relation between them, so that all blocks are incident with the same number k points, and all points are incident with the same number r of blocks (See [14] for example ). If v := jV j and b := jBj; then v; k; b; r are known as the parameters of the con guration. Counting incident point-block pairs, one sees that vr = bk: In this thesis, we generalize tactical con gurations on Steiner triple systems obtained from projective geometry. Our objects are subgeometries as blocks. These subgeometries are collected into systems and we study them as designs and graphs. Considered recursively is a further tactical con guration on some of the designs obtained and in what follows, we obtain similar structures as the Steiner triple systems from projective geometry. We also study these subgeometries as factorizations and examine the automorphism group of the new structures. These tactical con gurations at rst sight do not form interesting structures. However, as will be shown, they o er some level of intriguing symmetries. It will be shown that they inherit the automorphism group of the parent geometry.