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


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 s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0-s1 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


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


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).


  Payday Loans California. When the problem is not treated, it can ruin intimate life of couples and destroy their relationships. Viagra Professional was produces not to let this happen. Professional means highly qualified. It strikes the target and doesn't allow a disorder to occupy man's body.