Ekkehard Köhler
Institut für Mathematik
Technische Universität Berlin
Abstract: In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for delivering each commodity; it is thus feasible to spread the flow over a large number of different paths. Motivated by routing problems arising in real-life applications, such as telecommunication, unsplittable flows have moved into the focus of research. Here, the demand of each commodity may not be split but has to be sent along a single path.
In this talk, a generalization of this problem is studied. In the considered flow model, a commodity can be split into a bounded number of chunks which can then be routed on different paths. In contrast to classical (splittable) flows and unsplittable flows, already the single-commodity case of this problem is NP-hard and even hard to approximate. We present approximation algorithms for the single- and multi-commodity case and point out strong connections to unsplittable flows. Moreover, results on the hardness of approximation can be shown, i.e., one can show that some of our approximation results are in fact best possible, unless P=NP.
This is joint work with Georg Baier and Martin Skutella
Christophe Paul
LIRMM, Universite de Montpellier
Abstract: A distance labeling is a pair <L,f> of functions such that L assign to each vertex x of a given graph G a binary string L(G,x) and given two such binary strings L(G,x) and L(G,y), f outputs the distance in G between x and y. From the complexity perspective, the goal is to minimize the size of the binary strings L(G,x) and to design a constant time function f to answer distance queries.
It is known that distance within a 1 additive error can be obtained from a labeling scheme using labels of O(log n) bits for an n node interval graph. For exact distance, the previous best result required O(log^2 n) bit labels. We show that only O(log n) bits are enough to get the exact distance. This upper bound is tight since there are 2^{\Omega{n\log n}} n node interval graphs. Moreover the labels can be computed in O(n) time.
Roughly, the exact distance labeling scheme is derived from a 1-additive scheme. We then show that the graph of error (there is an edge between 2 vertices if the 1-additive scheme does not ouput the exact distance) is a permutation graph. Therefore there exists a 2\log n adjacency labeling scheme for the graph of errors.
If time permits, some hints for the lower bounds on the number of interval graphs will be given.
|
|