Greedy Algorithm

Pooja Gulia; Simran Bhatti; Vandana Tayal

doi:10.37591/rrdms.v2i2.415

Abstract

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning. A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage[1] with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time. Focusing on specific classes of problems we provide conditions under which our greedy procedure achieves the (nearly) minimum rate of convergence, implying that the procedure cannot be improved in a worst case setting. We also construct a fully adaptive procedure, which, without knowing the smoothness parameter of the decision boundary, converges at the same rate as if the smoothness parameter were known. Cite this Article:Pooja Gulia, Simran Bhatti, Vandana Tayal, Greedy Algorithm. Research & Reviews: Discrete Mathematical Structures. 2015; 2(2): 10–14p.