| [home] - [up] |
Abstract: We explain our view of algorithm engineering as a wider view of algorithmics that encompasses models, design, analysis, implementation of algorithms, experiments, algorithm libraries, and benchmarks. These activities form a tightly interacting methodology that encompasses but is more powerful than classical algorithm theory. Route planning in road networks is used as an example.
Colloquium - 16:00
Abstract: The Minimum Cycle Basis (MCB) Problem is a classical problem in combinatorial optimization. An $O(m^{2}n+mn^{2}\log{n})$-algorithm for this problem is known. Much faster heuristics have been examined in the context of several practical applications. These heuristics restrain the solution space to strictly fundamental cycle bases, hereby facing a significant loss in quality. We complement these experimental studies by giving theoretical evidence why strictly fundamental cycle bases (SFCB) in general must be much worse than general MCB.
Alon et al. (1995) provide the first non-trivial lower bound for the minimum SFCB problem, which in general is NP-hard. For unweighted planar square grid graphs they achieve a lower bound of $(ln 2)/2048 n\log_{2}n-O(n)$, where (ln 2)/2048 $\approx$ 1/2955.
Using a new recursive approach, we are able to establish a substantially better lower bound. Our explicit method yields a lower bound of only $1/12 n\log_{2}{n}-O(n)$. In addition, we provide an exact way of counting a short SFCB that was presented by Alon et al. In particular, we improve their upper bound from $2n\log_{2}n+o(n\log{n})$ to only~$4/3 n\log_{2}n-\Theta(n)$. We thus reduce the optimality gap for the MSFCB problem on planar square grids to a factor of 16 ---compared to about 5900 being the former state-of-the-art.
As a consequence, we conclude that for unweighted planar square grid graphs the ratio of the length of a minimum SFCB over a general MCB is $\Theta(\log{n})$.
Joint work with Ekkehard Köhler, Christian Liebchen, and Romeo Rizzi.