Improving greedy algorithms by lookahead-search

Sarkar, U. K. ; Chakrabarti, P. P. ; Ghose, S. ; Desarkar, S. C. (1994) Improving greedy algorithms by lookahead-search Journal of Algorithms, 16 (1). pp. 1-23. ISSN 0196-6774

Full text not available from this repository.

Official URL: http://linkinghub.elsevier.com/retrieve/pii/S01966...

Related URL: http://dx.doi.org/10.1006/jagm.1994.1001

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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:5918
Deposited On:19 Oct 2010 10:13
Last Modified:20 May 2011 09:48

Repository Staff Only: item control page