@techreport{Report-007-2006,
Title = {Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids},
Author = {Ekkehard K\"ohler and Christian Liebchen and Romeo Rizzi and Gregor W\"unsch},
Year = {2006},
Address = {Strasse des 17. Juni 136, 10623 Berlin},
Number = {007},
Month = {April},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
Abstract = {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\log 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 $\ln 2 /2048 n\log_2 n-O(n)$, where $ \ln 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\log_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\log_2 n$ to only $4/3 n\log_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.},
Url = {http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2006/Report-007-2006.pdf},
Keywords = {combinatorial optimization, cycle bases, strictly fundamental cycle bases, approximation, average stretch}
}