## Invited Session Fri.3.H 3010

#### Friday, 15:15 - 16:45 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Routing and shortest paths

**Chair: Nicole Megow**

**Friday, 15:15 - 15:40 h, Room: H 3010, Talk 1**

**Vincenzo Bonifaci**

Physarum can compute shortest paths

**Coauthors: Varma Girish, Kurt Mehlhorn**

**Abstract:**

*Physarum Polycephalum* is a slime mold that apparently is able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources *s*_{0} and *s*_{1}. We prove that, under this model, the mass of the mold will eventually converge to the shortest *s*_{0}-*s*_{1} path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution.

This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm'', that is, an algorithm developed by evolution over millions of years.

**Friday, 15:45 - 16:10 h, Room: H 3010, Talk 2**

**Jannik Matuschke**

Approximation algorithms for capacitated location routing

**Coauthors: Tobias Harks, Felix G. König**

**Abstract:**

Location routing integrates the two classical optimization problems of facility location and vehicle routing, addressing both location decisions and tour planning in a single step. Given a graph whose vertex set consists of facilities and clients with given demands, the problem is to find a subset of facilities that have to be opened, and a set of tours originating from those facilities, serving all clients while at the same time respecting the (uniform) capacity limitation of the vehicles in use, and minimizing the incurred opening and connection costs.

We derive the first polynomial time constant factor approximation for capacitated location routing and some variants of the problem, including cross-docking, prize-collecting, and a group variant. Our results originate from combining algorithms and lower bounds for different relaxations of the original problem.

Finally, we present a computational study on popular benchmark instances from the literature and newly generated large-scale random instances. It turns out that, in practice, solutions of our algorithm are much closer to optimality than guaranteed by the theoretical approximation factor.

**Friday, 16:15 - 16:40 h, Room: H 3010, Talk 3**

**Rene Sitters**

Metrical service systems and the generalized work function algorithm

**Abstract:**

There are some very intriguing open problems in online optimization. Examples are the *k*-server conjecture (deterministic and randomized) and the dynamic search tree conjecture (dynamic optimality conjecture). Both problems are in the class of metrical service systems (online shortest path problems). It is widely believed that dynamic search trees are constant competitive. We show some strong techniques for proving constant competitiveness of metrical service systems and develop a universal theory of competitive analysis of metrical service systems. In particular, we apply this to the generalized *2*-server problem and show that the generalized work function algorithm is onstant competitive in any metric space, as was conjectured by Koutsoupias and Taylor (2004).