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.


Selected Publications

A. A. Bock; K. Chandrasekaran; J. Könemann; B. Peis; L. Sanità : Finding small stabilizers for unstable graphs. 2014. Integer Programming and Combinatorial Optimization (IPCO), Bonn, Germany, June 2014.
A. A. Bock; L. Sanità : On the approximability of two capacitated vehicle routing problems. 2013. International Network Optimization Conference (INOC), Tenerife, Spain, May 20-22, 2013. p. 519 - 526. DOI : 10.1016/j.endm.2013.05.133.
N. Haehnle; L. Sanita; R. Zenklusen : Stable Routing And Unique-Max Coloring On Trees; Siam Journal On Discrete Mathematics. 2013. DOI : 10.1137/100817565.
J. Byrka; F. Grandoni; T. Rothvoss; L. Sanità : Steiner Tree Approximation via Iterative Randomized Rounding; Journal of the ACM. 2013. DOI : 10.1145/2432622.2432628.
A. A. Bock; E. Grant; J. Könemann; L. Sanità : The School Bus Problem on Trees; Algorithmica -New York-. 2012. DOI : 10.1007/s00453-012-9711-x.
F. Grandoni; T. Rothvoss; L. Sanita : From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk; Mathematics Of Operations Research. 2011. DOI : 10.1287/moor.1110.0490.
A. A. Bock; E. Grant; J. Könemann; L. Sanità : The School Bus Problem on Trees. 2011. 22nd International Symposium on Algorithms and Computation (ISAAC 2011), Yokohama, Japan, December 5-8, 2011. p. 10-19.
F. Grandoni; G. Nicosia; G. Oriolo; L. Sanità : Stable routing under the Spanning Tree Protocol; Operations Research Letters. 2010. DOI : 10.1016/j.orl.2010.05.001.
J. Byrka; F. Grandoni; T. Rothvoß; L. Sanità : An Improved LP-based Approximation for Steiner Tree. 2010. 42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, Massachusetts, USA, June 6-8, 2010.
S. Fiorini; G. Oriolo; L. Sanità; D. O. Theis : The VPN problem with concave costs; Siam Journal of Discrete Mathematics. 2010. DOI : 10.1137/090749700.
T. Rothvoß; L. Sanità : On the Complexity of the Asymmetric VPN Problem. 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.