Abstract of article "k-greedy algorithms for independence systems"

Recently in Jenkyns [1976] and Korte/Hausmann [1978] a tight worst-case bound for the well-known greedy heuristic for general independence systems has been deduced. Here some modifications of the greedy heuristic are investigated which allow to enlarge the current independent set by more than one element. It is shown that in spite of the additional enumeration incorporated in these heuristics they can behave worse than the usual greedy heuristic for some problem instances. For one of those modifications the same worst-case bound as mentioned above — but no better one — has been proved again. These results underline the predominant role of the usual greedy heuristic for general independence systems.