Network Optimization

Abstract

We study fundamental mathematical problems originating form the field of Network Optimization.

There are plenty of networks (e.g. electrical, communication, transportation, computer networks), whose efficiency is crucial. Typically, the geometry of the underlying problem is modeled as a graph G=(V,E) and the problem is to install elements of the constructed network in vertices and edges of G. Constructing an element incurs a certain cost which may depend on the location in G. We aim at obtaining a minimal cost network having all the required properties.

Such interesting network problems are mostly NP-hard, so it is unlikely that efficient algorithms for finding optimal solutions for these problems exist. We concentrate on efficiently finding close to optimal solutions by means of approximation algorithms.

An important field of network optimization problems is related to Network Design problems, where we are given a set of nodes of the graph (called terminals) that want to communicate with each other, and we need to buy some edges of the graph to connect all the terminals. Famous examples could be Steiner Tree problem, or Virtual Private Network design problems. Still, in case of economies of scale in buying capacities, the total installation cost could be modeled as a concave function: classical examples are buy-at-bulk problems or rent-or-buy problems. We concentrate on developing constant approximation algorithms for such problems and settle some important compexity issues.

Another field is related to Location problems: a relevant example is the Facility Location Problem, where we need to install facilities in vertices of the graph in order to service a given set of clients. Opening a facility incurs a location specific cost, servicing a client with a facility contributes a cost proportional to the client-facility distance.

We studied the basic variant of the problem called metric Uncapacitated Facility Location, and the more general Connected Facility Location problem, where we also need to connect all the facilities, which incurs cost proportional to the total length of the edges used to connect them. We give constant factor approximation algorithms for both the variants.

Members

Jarosław Byrka

Friedrich Eisenbrand

Thomas Rothvoß

Laura Sanità

Selected Publications

Network Design via Core Detouring for Problems Without a Core

F. Grandoni; T. Rothvoss 

2010. 37th International Colloquium on Automata, Languages and Programming (ICALP'10), Bordeaux, France, July 5-10, 2010. p. 490-502. DOI : 10.1007/978-3-642-14165-2_42.

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.

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.

Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm

J. Byrka; A. Srinivasan; C. Swamy 

2010. 14th Conference on Integer Programming and Combinatorial Optimization, Lausanne, June 9-11, 2010.

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.

Approximating connected facility location problems via Random facility sampling and core detouring

F. Eisenbrand; F. Grandoni; T. Rothvoß; G. Schäfer 

2008. ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, California, 20-22.01.2008. p. 1174-1183.

New approaches for virtual private network design

F. Eisenbrand; F. Grandoni; G. Oriolo; M. Skutella 

SIAM Journal on Computing. 2007. Vol. 37, num. 3, p. 706-721 (electronic). DOI : 10.1137/060654827.