Improving greedy algorithms by lookahead-search

Abstract

This paper shows that repeated application of a greedy approximation algorithm on some suitably selected subproblems of a problem often leads to a solution which is better than the solution produced by the greedy algorithm applied to the original problem. The lookahead search technique, a polynomial time algorithm introduced here, describes how a greedy algorithm can be utilized in a search process in order to improve the quality of the solution. For the 0/1 knapsack problem and the problem of scheduling independent tasks the lookahead technique is shown to guarantee ε-bounded solutions. For the problem of scheduling independent tasks, it has been established that even the simplified version of the lookahead technique provides a bound which is strictly better than the greedy algorithm used in lookahead search. Experimental results are shown for 0/1 knapsack problem, bin packing, Euclidean TSP, and the problem of scheduling independent tasks.