Robust Network Design


Swiss National Science Foundation (SNSF)


Friedrich Eisenbrand

Adrian Bock

Jarosław Byrka

Thomas Rothvoß

Laura Sanità


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.

Selected Publications

Finding small stabilizers for unstable graphs

A. A. Bock; K. Chandrasekaran; J. Könemann; B. Peis; L. Sanità 

2014. Integer Programming and Combinatorial Optimization (IPCO), Bonn, Germany, June 2014.

On the approximability of two capacitated vehicle routing problems

A. A. Bock; L. Sanità 

2013. International Network Optimization Conference (INOC), Tenerife, Spain, May 20-22, 2013. p. 519-526. DOI : 10.1016/j.endm.2013.05.133.

The School Bus Problem on Trees

A. A. Bock; E. Grant; J. Könemann; L. Sanità 

Algorithmica. 2013. Vol. 67, num. 1, p. 49-64. DOI : 10.1007/s00453-012-9711-x.

Stable Routing And Unique-Max Coloring On Trees

N. Haehnle; L. Sanita; R. Zenklusen 

Siam Journal On Discrete Mathematics. 2013. Vol. 27, num. 1, p. 109-125. DOI : 10.1137/100817565.

Steiner Tree Approximation via Iterative Randomized Rounding

J. Byrka; F. Grandoni; T. Rothvoss; L. Sanità 

Journal of the ACM. 2013. Vol. 60, num. 1, p. 6. DOI : 10.1145/2432622.2432628.

From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk

F. Grandoni; T. Rothvoss; L. Sanita 

Mathematics Of Operations Research. 2011. Vol. 36, p. 185-204. DOI : 10.1287/moor.1110.0490.

The School Bus Problem on Trees

A. A. Bock; E. Grant; J. Könemann; L. Sanità 

2011. 22nd International Symposium on Algorithms and Computation (ISAAC 2011), Yokohama, Japan, December 5-8, 2011. p. 10-19. DOI : 10.1007/978-3-642-25591-5_3.

Stable routing under the Spanning Tree Protocol

F. Grandoni; G. Nicosia; G. Oriolo; L. Sanità 

Operations Research Letters. 2010. Vol. 38, num. 5, p. 399-404. DOI : 10.1016/j.orl.2010.05.001.

An Improved LP-based Approximation for Steiner Tree

J. Byrka; F. Grandoni; T. Rothvoß; L. Sanità 

2010. 42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, Massachusetts, USA, June 6-8, 2010. p. 583–592. DOI : 10.1145/1806689.1806769.

The VPN problem with concave costs

S. Fiorini; G. Oriolo; L. Sanità; D. O. Theis 

Siam Journal of Discrete Mathematics. 2010. Vol. 24, num. 3, p. 1080-1090. DOI : 10.1137/090749700.

On the Complexity of the Asymmetric VPN Problem

T. Rothvoß; L. Sanità 

2009. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX ’09), UC Berkeley, USA, August 21-23, 2009. p. 326-338. DOI : 10.1007/978-3-642-03685-9_25.