Open Access Open Access  Restricted Access Subscription Access

Greedy Algorithm

Pooja Gulia, Simran Bhatti, Vandana Tayal

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.


Full Text:

PDF

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.


Refbacks

  • There are currently no refbacks.


This site has been shifted to https://stmcomputers.stmjournals.com/