direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2006

Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids
Zitatschlüssel Report-007-2006
Autor Ekkehard Köhler and Christian Liebchen and Romeo Rizzi and Gregor Wünsch
Jahr 2006
Adresse Strasse des 17. Juni 136, 10623 Berlin
Nummer 007
Monat April
Institution Technische Universität Berlin, Institut für Mathematik
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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag