Improving Greedy Algorithms by Lookahead-Search

✍ Scribed by U.K. Sarkar; P.P. Chakrabarti; S. Ghose; S.C. Desarkar

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 967 KB
• Volume: 16
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1994.1001

✦ Synopsis

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 (\varepsilon)-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. 1994 Academic Press, Inc.