Loading…
Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids
Köhler, Ekkehard; Liebchen, Christian; Rizzi, Romeo; Wünsch, Gregor
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
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 explaining theoretically why strictly fundamental cycle bases~(SFCB) in general must be much worse than general MCB.
