[home] - [up]


Lectures and Colloquia during the semester



January 23, 2006

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041           - map -
Lecture - 14:15

Thomas Erlebach -University of Leicester

Network Discovery and Verification

Abstract: Motivated by attempts to discover the topology of large networks such as the Internet or peer-to-peer networks, we model the network discovery problem as the combinatorial optimization problem of discovering an unknown graph using a minimum number of queries. In the layered-graph query model, a query at a vertex returns the shortest-path subgraph rooted at that node. In the distance query model, a query at a vertex returns the distances to all other nodes. The discovery algorithm is required to select the next query based only on the information it has already obtained with previous queries. The discovery process is completed when all edges and non-edges of the graph are known. For both query models, we present upper and lower bounds on the best possible competitive ratio that can be achieved by an algorithm. Moreover, we study the off-line version of the problems, where complete information about the graph is given in advance and the goal is to compute an optimal query set. This is motivated by the problem of verifying whether a given map of the network is correct. We present complexity results, inapproximability results, and simple approximation algorithms. For the layered-graph query model, it turns out that the optimal number of queries corresponds to the metric dimension of the graph. Joint work with: Zuzana Beerliova, Felix Eberhard, Alexander Hall and L. Shankar Ram (ETH Zürich); Michael Hoffmann and Matus Mihalak (University of Leicester).


Colloquium - 16:00

Guido Schäfer - Technische Universität Berlin

A Simple 5-Approximation Algorithm for Multicommodity Rent-or-Buy

Abstract: In the multicommodity rent-or-buy network design problem (MRoB) we are given a network together with k terminal pairs (si, ti). The goal is to install capacities on the edges of the network so that a prescribed amount of flow fi can be routed between all terminal pairs si and ti simultaneously. We can either rent capacity on an edge at some cost per unit flow or buy infinite capacity on an edge at some larger fixed cost. The overall objective is to install capacities at a minimum total cost.

Gupta et al. (FOCS '03) gave a randomized scheme for the MRoB problem that has been used subsequently to improve the approximation ratio for this problem. The currently best known 6.82-approximation algorithm is due to Becchetti et al. (SODA '05).

We present a surprisingly simple 5-approximation algorithm for MRoB and show that this is nearly tight in the following sense: No approximation ratio better than 4.66 can be achieved using the above mentioned randomized scheme in combination with the currently best known Steiner forest approximation algorithms.

Joint work with: Lisa Fleischer (IBM Watson), Jochen Könemann (University of Waterloo), Stefano Leonardi (University of Rome "La Sapienza")


[home] - [up] - [top]