The Steiner tree problem is a classical, well-studied, $\mathcal{NP}$-hard optimization problem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ of terminals, and non-negative costs $c_e$ for all edges $e$ in $E$. A feasible Steiner tree for a given instance is a tree $T$ in $G$ that spans all terminals in $R$. The goal is to compute a feasible Steiner tree of smallest cost. In this thesis we will focus on approximation algorithms for this problem: a $c$-approximation algorithm is an algorithm that returns a tree of cost at most $c$ times that of an optimum solution for any given input instance. <br /><br /> In a series of papers throughout the last decade, the approximation guarantee $c$ for the Steiner tree problem has been improved to the currently best known value of 1. 55 (Robins, Zelikovsky). Robins' and Zelikovsky's algorithm as well as most of its predecessors are greedy algorithms. <br /><br /> Apart from algorithmic improvements, there also has been substantial work on obtaining tight linear-programming relaxations for the Steiner tree problem. Many undirected and directed formulations have been proposed in the course of the last 25 years; their use, however, is to this point mostly restricted to the field of exact optimization. There are few examples of algorithms for the Steiner tree problem that make use of these LP relaxations. The best known such algorithm for general graphs is a 2-approximation (for the more general Steiner forest problem) due to Agrawal, Klein and Ravi. Their analysis is tight as the LP-relaxation used in their work is known to be weak: it has an IP/LP gap of approximately 2. <br /><br /> Most recent efforts to obtain algorithms for the Steiner tree problem that are based on LP-relaxations has focused on directed relaxations. In this thesis we present an undirected relaxation and show that the algorithm of Robins and Zelikovsky returns a Steiner tree whose cost is at most 1. 55 times its optimum solution value. In fact, we show that this algorithm can be viewed as a primal-dual algorithm. <br /><br/> The Steiner forest problem is a generalization of the Steiner tree problem. In the problem, instead of only one set of terminals, we are given more than one terminal set. An feasible Steiner forest is a forest that connects all terminals in the same terminal set for each terminal set. The goal is to find a minimum cost feasible Steiner forest. In this thesis, a new set of facet defining inequalities for the polyhedra of the Steiner forest is introduced.

The Steiner tree problem is a classical, well-studied, $\mathcal{NP}$-hard optimization problem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ of terminals, and non-negative costs $c_e$ for all edges $e$ in $E$. A feasible Steiner tree for a given instance is a tree $T$ in $G$ that spans all terminals in $R$. The goal is to compute a feasible Steiner tree of smallest cost. In this thesis we will focus on approximation algorithms for this problem: a $c$-approximation algorithm is an algorithm that returns a tree of cost at most $c$ times that of an optimum solution for any given input instance. <br /><br /> In a series of papers throughout the last decade, the approximation guarantee $c$ for the Steiner tree problem has been improved to the currently best known value of 1. 55 (Robins, Zelikovsky). Robins' and Zelikovsky's algorithm as well as most of its predecessors are greedy algorithms. <br /><br /> Apart from algorithmic improvements, there also has been substantial work on obtaining tight linear-programming relaxations for the Steiner tree problem. Many undirected and directed formulations have been proposed in the course of the last 25 years; their use, however, is to this point mostly restricted to the field of exact optimization. There are few examples of algorithms for the Steiner tree problem that make use of these LP relaxations. The best known such algorithm for general graphs is a 2-approximation (for the more general Steiner forest problem) due to Agrawal, Klein and Ravi. Their analysis is tight as the LP-relaxation used in their work is known to be weak: it has an IP/LP gap of approximately 2. <br /><br /> Most recent efforts to obtain algorithms for the Steiner tree problem that are based on LP-relaxations has focused on directed relaxations. In this thesis we present an undirected relaxation and show that the algorithm of Robins and Zelikovsky returns a Steiner tree whose cost is at most 1. 55 times its optimum solution value. In fact, we show that this algorithm can be viewed as a primal-dual algorithm. <br /><br/> The Steiner forest problem is a generalization of the Steiner tree problem. In the problem, instead of only one set of terminals, we are given more than one terminal set. An feasible Steiner forest is a forest that connects all terminals in the same terminal set for each terminal set. The goal is to find a minimum cost feasible Steiner forest. In this thesis, a new set of facet defining inequalities for the polyhedra of the Steiner forest is introduced.

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 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.

<p>We start by slightly modifying the generic framework for solving online covering and packing linear programs (LP) proposed in the seminal work of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) to obtain efficient implementations in settings in which one has access to a separation oracle.</p> <p><br></p> <p>We then apply the generic framework to several online network connectivity problems with LP formulations, namely pairwise spanners and directed Steiner forests. Our results are comparable to the previous state-of-the-art results for these problems in the offline setting.</p> <p><br></p> <p>Further, we extend the generic frameworks to online optimization problems enhanced with <strong>machine-learning predictions</strong>. In particular, we present <strong>learning-augmented</strong> algorithms for online covering LPs and semidefinite programs (SDP), which outperform any optimal online algorithms when the prediction is accurate while maintaining reasonable guarantees when the prediction is misleading. Specifically, we obtain general online learning-augmented algorithms for covering LPs with fractional advice and general constraints and initiate the study of learning-augmented algorithms for covering SDPs.</p>