| Zusammenfassung |
The Minimum Cycle Basis (MCB) Problem is a classical problem in combinatorial optimization. This problem can be solved in $O(m^2 n+mn^2łog n)$. 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 explaning theoretically 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 $łn 2 /2048 nłog_2 n-O(n)$, where $ łn 2 / 2048\approx 1/2955$. Introducing 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łog_2 n+O(n)$. In addition, we provide an accurate way of counting a short strictly fundamental cycle basis that was presented by Alon et al. In particular, we improve their upper bound from $2nłog_2 n$ to only $4/3 nłog_2 n$. We finally conclude that these bases miss the optimum only by a factor of at most $16$–-compared to about $5900$ according to Alon et al. |
