Greedy Algorithm

Authors

  • Pooja Gulia Department of Computer Science Engineering, Dronacharya College of Engineering, Karnal, Haryana India
  • Simran Bhatti Department of Computer Science Engineering, Dronacharya College of Engineering, Karnal, Haryana India
  • Vandana Tayal Department of Computer Science Engineering, Dronacharya College of Engineering, Karnal, Haryana India

DOI:

https://doi.org/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.

References

Cormen, Thomas, Charles E Leiserson, Ronald L Rivest, Clifford Stein. Introduction To Algorithms (Third ed.). MIT Press.

Kruskal, J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society.

van S. de Geer. Empirical Processes in M-Estimation. A.W.

van der Vaart and J.A. Wellner. Weak Convergence and Empirical Processes.

Vapnik V. N.. Estimation of Dependences Based on Empirical Data.

Yang Y. Statistical Learning Theory. Minimax nonparametric classification - part I: rates of convergence. IEEE Trans. Inf. TheoryT.

Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. Ann. Statis. Accepted for publication.

Zhang T. Sequential greedy approximation for certain convex optimization problems. IEEE Tran.

Downloads

Published

2015-06-29

Issue

Vol. 2 No. 2 (2015)

Section

Review Articles

License

Declaration and Copyright Transfer Form

(to be completed by authors)

I/ We, the undersigned author(s) of the submitted manuscript, hereby declare, that the above manuscript which is submitted for publication in the STM Journals(s), is not published already in part or whole (except in the form of abstract) in any journal or magazine for private or public circulation, and, is not under consideration of publication elsewhere.

  • I/We will not withdraw the manuscript after 1 week of submission as I have read the Author Guidelines and will adhere to the guidelines.
  • I/We Author(s ) have niether given nor will give this manuscript elsewhere for publishing after submitting in STM Journal(s).
  • I/ We have read the original version of the manuscript and am/ are responsible for the thought contents embodied in it. The work dealt in the manuscript is my/ our own, and my/ our individual contribution to this work is significant enough to qualify for authorship.
  •  I/We also agree to the authorship of the article in the following order:

Author’s name                                    

 

1. ________________

2. ________________

3. ________________

4. ________________

 

We  Author(s) tick this box and would request you to consider it as our signature as we agree to the terms of this Copyright Notice, which will apply to this submission if and when it is published by this journal.