Robust Network Design

Network Design deals with the reservation of capacities at minimum cost on the edges of a network such that a set of terminals can communicate with each other. Difficult problems of this kind have to be solved frequently by network service providers. Efficient solvers for network design problems are therefore an important algorithmic tool with a high technological and economic impact.

A typical scenario is that of buying min cost capacity to guarantee connectivity from a subset of terminals of the network to a certain central switch node. In many of these cases, buying capacity often reflects an economy of scale principle: the more capacity is installed, the cheaper is the price per unit. Such concave costs add to the difficulty in finding an optimal or near optimal solution.

Still, in classical and well studied settings one assumes that the communication patterns are known and fixed. However, in many relevant application scenarios, like for example IP networks, those communication patterns are hard to predict and rapidly change over time. Therefore, operators often know only that the set of communication patterns comes from some bounded universal set of inputs. In these cases, a robust solution is one able to support any set of communication patterns that belongs to the given universal set.

The goal pursued in this project is to advance the state-of-the-art of solving robust network design problems and to design, analyze and implement efficient algorithms for such networks.