direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 07-2006

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids
primary: 90C27 Combinatorial optimization
secondary: 68R05 Combinatorics
05C05 Trees
05C38 Paths and cycles
combinatorial optimization, cycle bases, strictly fundamental cycle bases, approximation, average stretch
The Minimum Cycle Basis~(MCB) Problem is a classical problem in combinatorial optimization. This problem can be solved in O(m2n+mn2log(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 log2n-O(n), where ln(2)/2048 ≈ 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 log2n+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 log2n to only 4/3 n log2n. 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.
Download as [PDF]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe