Invited Session Thu.1.H 3002

Thursday, 10:30 - 12:00 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Networks in production, logistics and transport


Chair: Sven Oliver Krumke



Thursday, 10:30 - 10:55 h, Room: H 3002, Talk 1

Sabine Büttner
Online network routing amongst unknown obstacles


We consider variants of online network optimization problems connected to graph exploration. In the prize-collecting travelling salesman problem, we are given a weighted graph G = (V,E) with edge weights l : E → R+, a special vertex r ∈ V, penalties p:V → R+ and the goal is to find a closed tour~T such that r ∈ V(T) and such that the cost l(T)+p(V \ V(T)) is minimized. In an online variant, which we call the Canadian Tour Operator Problem (CTOP), the task is to route a tourist bus through a given network G = (V, E) in which some edges are blocked by avalanches. An online algorithm learns from a blocked edge only when reaching one of its endpoints. The bus operator has the option to avoid visiting each node v ∈ V by paying a refund of p(v) to the tourists. The goal is to minimize the sum of the travel costs and the refunds. We show that no deterministic or randomized algorithm can achieve a bounded competitive ratio for the CTOP on general graphs and give O(1)-competitive algorithms for special networks. We also relate the problem to other (classical) online network and routing problems.



Thursday, 11:00 - 11:25 h, Room: H 3002, Talk 2

Thomas Werth
Bottleneck routing games

Coauthors: Sven O. Krumke, Heike Sperber


We consider Nash and strong equilibria in weighted bottleneck routing games in single commodity networks.
In such a game every player chooses a path from the common source vertex to the sink vertex in a graph with directed edges.
The cost of an edge depends on the total weight of players choosing it
and the personal cost every player tries to minimize
is the cost of the most expensive edge in her path, the bottleneck value.
To derive efficient algorithms for finding equilibria in unweighted games, we generalize a transformation of a bottleneck game into a special congestion game introduced by Caragiannis et al. (2005).
For weighted routing games we show that Greedy methods give Nash equilibria in extension-parallel and series-parallel graphs.
On the other hand, computing a strong equilibrium is co-NP complete in general graphs, even for linear latency functions.
Furthermore, we show that the Price of Anarchy can be arbitrarily high for different situations and give tight bounds depending on the topology, the number and weights of the users and the degree of the polynomial latency functions.



Thursday, 11:30 - 11:55 h, Room: H 3002, Talk 3

Marco Bender
Online delay management: Beyond competitive analysis

Coauthors: Sabine Büttner, Sven O. Krumke


We consider the Online Delay Management Problem on a network with a path topology that is served by one train. In this problem the number of delayed passengers is not known beforehand but revealed in an online fashion. The goal is to decide at which station a train should wait in order to minimize the total delay of all passengers.
We introduce the concept of a lookahead which yields information about delays at succeeding stations. Although this does not lead to better competitive ratios, we can justify the intuition that it is a feature that does help an algorithm. To this end, we make use of comparative analysis that allows to compare different classes of lookahead algorithms with each other.

Furthermore, we show how knowledge about the distributions of delayed passengers can be used in order to set up a stochastic programming framework.


  The system of instant Virginia Payday Loans allows any adult U.S. citizen. If you have already decided to take Levitra For Sale, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.