## Invited Session Thu.1.H 3005

#### Thursday, 10:30 - 12:00 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Robust network design

**Chair: Michael Juenger**

**Thursday, 10:30 - 10:55 h, Room: H 3005, Talk 1**

**Manuel Kutschka**

Robust metric inequalities for network design under demand uncertainty

**Coauthors: Grit Claßen, Arie Mca Koster, Issam Tahiri**

**Abstract:**

In this talk, we generalize the metric inequalities for the (classical)

network design problem to its robust counter-part. Furthermore, we

show that they describe the robust network design problem completely

in the capacity space, where a straight-forward generalization of the

classical metric inequalities is not sufficient.

We present a polynomial algorithm to separate robust metric in-equalities as model inequalities for the capacity space formulation of

the robust network design problem. In computational experiments, we

analyze the added value of this new class of valid inequalities within a

branch-and-cut approach to solve the robust network design problem.

**Thursday, 11:00 - 11:25 h, Room: H 3005, Talk 2**

**Daniel R. Schmidt**

Single commodity robust network design: Models and algorithms

**Coauthors: Eduardo Alvarez-Miranda, Valentina Cacchiani, Tim Dorneth, Michael Jünger, Frauke Liers, Andrea Lodi, Tiziano Parriani**

**Abstract:**

We study a model that aims at designing cost-minimum networks that are robust under varying demands: Given an undirected graph *G*, a finite number of scenarios and a cost function, we want to find the cheapest possible capacity installation on the edges of *G* such that the demands of all scenarios can be satisfied by a single-commodity flow. This problem is known in the literature as *single commodity robust network design*. We propose two tools for optimizing over this model: Firstly, we develop a large neighborhood search heuristic that allows for trading computing time for solution quality. Secondly, we show how to optimize exactly with a branch-and-cut algorithm that is based on a new integer programming formulation. Both approaches undergo computational evaluation.

**Thursday, 11:30 - 11:55 h, Room: H 3005, Talk 3**

**Laura Sanità**

Steiner tree approximation via iterative randomized rounding

**Coauthors: Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoss**

**Abstract:**

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from *2* to *1.55* [Robins,Zelikovsky-'05]. All these algorithms are purely combinatorial.

In this talk we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most *ln(4)+ε<1.39* times the cost of an optimal Steiner tree.