Till Fluschnik

Till Fluschnik, Amela Pucic, Malte Renken

Motivated by evacuation scenarios arising in extreme events such as flooding or forest fires, we study the problem of smoothly scheduling a set of paths in graphs where connections become impassable at some point in time. A schedule is smooth if no two paths meet on an edge and the number of paths simultaneously located at a vertex does not exceed its given capacity. We study the computational complexity of the problem when the underlying graph is a tree, in particular a star or a path. We prove that already in these settings, the problem is NP-hard even with further restrictions on the capacities or on the time when all connections ceased. We provide an integer linear program (ILP) to compute the latest possible time to evacuate. Using the ILP and its relaxation, we solve sets of artificial (where each underlying graph forms either a path or star) and semi-artificial instances (where the graphs are obtained from German cities along rivers), study the runtimes, and compare the results of the ILP with those of its relaxation.

Markus Brill, Till Fluschnik, Vincent Froese et al.

Dynamic time warping constitutes a major tool for analyzing time series. In particular, computing a mean series of a given sample of series in dynamic time warping spaces (by minimizing the Fréchet function) is a challenging computational problem, so far solved by several heuristic and inexact strategies. We spot some inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Our contributions comprise an exact dynamic program computing a mean (useful for benchmarking and evaluating known heuristics). Based on this dynamic program, we empirically study properties like uniqueness and length of a mean. Moreover, experimental evaluations reveal substantial deficits of state-of-the-art heuristics in terms of their output quality. We also give an exact polynomial-time algorithm for the special case of binary time series.