DiscMathMeeting: Battlezone (Edda on Virtual Private Networks)

where speakers would present a talk they planned to give at a
conference and then hope to get useful feed-back. However, my feeling
is that in many cases the audience was too shy or too lazy to give the
appropriate feed-back. As discussed in the previous DMM, I hope to
overcome this with the following event.

The DMM-Battlezone (thanks to Martin for this name and
enthusiastically coorganizing) is a subseries of the
DiscMathMeeting. Here, volunteers may give a practise talk, which
subsequently is thoroughly analyzed by the audience. It is hence
understood by all participants that

- the speaker asks for clear comments on all aspects of the talk. To
make this most effective, he/she is well-prepared to the utmost he/she
is capable of on his/her own (in other words, we don't prepare your
talk, and you don't start to cry if we don't like your talk);

- the audience attends to learn how to give talks and to helps others
to give good talks. To this end, no-one should be shy to give also
negative feed-back. Martin and I facilitate this event, but we are not
the teachers here (though, of course, we may also give comments),

- the DMM-Battlezone does not replace the Mittagsseminar as means of
communication recent own work. The speaker will present his/her work there
or at another appropriate meeting as well (presumably some time after
the Battlezone).


This time: Edda is the first volunteer. The details of her talk are:

Title: Provisioning a Virtual Private Network Under the Presence of
Non-communicating Groups


Abstract: Virtual private network design in the hose model deals with
the reservation of capacities in a weighted graph such that the
terminals in this network can communicate with one another. Each
terminal is equipped with an upper bound on the amount of traffic that
the terminal can send or receive. The task is to install capacities at
minimum cost and to compute paths for each unordered terminal pair
such that each valid traffic matrix can be routed along those paths.

In this paper we consider a variant of the virtual private network
design problem which generalizes the previously studied symmetric and
asymmetric case. In our model the terminal set is partitioned into a
number of groups, where terminals of each group do not communicate
with each other.

Our main result is a 4.74 approximation algorithm for this problem.