Thumbnail Image

Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids

Köhler, Ekkehard; Liebchen, Christian; Rizzi, Romeo; Wünsch, Gregor

Inst. Mathematik

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.