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


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


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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.