Köhler, EkkehardLiebchen, ChristianRizzi, RomeoWünsch, Gregor2021-12-172021-12-1720062197-8085https://depositonce.tu-berlin.de/handle/11303/15599http://dx.doi.org/10.14279/depositonce-14372The 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.en510 Mathematikcombinatorial optimizationcycle basesstrictly fundamental cycle basesapproximationaverage stretchResearch Paper