Analysis The Time Complexity of Greedy Algorithm Used in Optimization  
  Authors : Yogesh Chanchal; Dr. Ashendra Kumar Saxena

 

My idea behind this research is to find a new greedy way to find the optimal solution in Euclidean space .Today we face many real life complex problems, to solve real life of complex problem we developed a new greedy approach in minimum time. Here we have find the time complexity of algorithm (Kruskal, Prims, Dijkastra, Tsp) and have compared following algorithms with each other. Our main goal to find the best case time complexity for both Minimum Spanning Tree (MST) and Single Source Shortest Path (SSST).Both Approaches MST and SSSP have been used in greedy approach. In this research paper, we have developed same way for same approach with reduced time complexity which provides best case time complexity for any weighted graph in Euclidean space. We have developed an algorithm that manipulates the greedy approach for a set of n points in a metric space with corresponding doubling dimension. Suppose G (V, E, w) is a simple graph where V denotes a set of Vertices in a given graph and E denotes set of edges of a graph and vertices are connected with edges. All edges having non negative weight which also represent distance between two nodes in a given graph. To remember greedy approach as we developed a new greedy approach to find the shortest route among nodes or vertices. Which gives an optimal way in minimum time among nodes or vertices? Here we have worked the concept of MST and SSSP. Simply this research is based on combinatorial optimization and focused to find the optimum solution of various types of general problems.

 

Published In : IJCAT Journal Volume 2, Issue 7

Date of Publication : July 2015

Pages : 227 - 231

Figures :07

Tables : --

Publication Link :Analysis The Time Complexity of Greedy Algorithm Used in Optimization

 

 

 

Yogesh Chanchal : has done B.Tech in computer science stream from Uttar Pradesh Technical university. I have 1 year teaching experience from somany institute of Technology and management college, Rewari , Haryana. Now I am pursuing M.Tech in computer science stream at Teerthanker Mahaveer University Moradabad

Dr. Asherdra Kumar Saxena : has done Ph.D. in the area of applied mathematics from MJP Rohilkhand University, Bareilly. I completed M.Phill in computer Science from Alagappa University Tamilnadu and MCA degree from Uttar Pradesh Technical University Lucknow in 2003. I completed M.Sc. in Mathematics from MJP Rohilkhand University, Bareilly in 1997. I am working in Teerthanker Mahaveer University, Moradabad (U.P.), from July 2003 to till date. At present, I am Associate Professor & HOD in College of Computing Sciences and Information Technology, Teerthanker Mahaveer University, Moradabad (U.P.). I have 12 years of experience in teaching, administration. I have published 15 papers in International Journals / Conferences and 10 papers in National Journal / Conferences. My research interest includes solving the different problems in networks using Optimization Techniques, Algorithm design and reducing the complexity of algorithms.

 

 

 

 

 

 

 

Greedy Algorithms

Greedy Approaches

Minimum Spanning Tree

Single Source Shortest Path

mobile communication

Approximate Solutions

Time Complexity

The yTSP and yKRUSKAL exists at the top of our Operational Research. Both algorithms describe many practical applications and its study over the many years or so has led to important theoretical developments. Problems having a few numbers of vertices can now be solved routinely to optimality. Instances involving more than 100s of vertices have also been solved exactly by means of constraint yTSP and yKRUSKAL algorithms. A number of important heuristics also proposed both search methods and generalized insertion algorithms appear to hold much potential.

 

 

 

 

 

 

 

 

 

[1] I. Althofer, G. Das, D. P. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete and Computational Geometry, 9(1):81–100, 1993. [2] P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to knearest- neighbors and n-body potential fields. Journal of the ACM, 42:67–90, 1995. [3] B. Chandra. Constructing sparse spanners for most graphs in higher dimensions. Information Processing Letters, 51(6):289–294, 1994. [4] B. Chandra, G. Das, G. Narasimhan, and J. Soares. New sparseness results on graph spanners. International Journal of Computational Geometry and Applications, 5:124– 144, 1995. [5] L. P. Chew. There is a planar graph almost as good as the complete graph. In SCG ’86: Proceedings of the 2nd Annual ACM Symposium on Computational Geometry, pages 169–177, 1986. [6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, 2nd edition, 2001. [7] G. Das, P. J. Hagerman, and G. Narasimhan. Optimally sparse spanners in 3-dimensional Euclidean space. In SCG’93: Proceedings of the 9th Annual ACM Symposium on Com- putational Geometry, pages 53–62, 1993. [8] G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. International Journal of Computational Geometry and Applications, 7:297–315, 1997. [9] E. W. Dijkstra. A note on two problems in connection with graphs. Numeric Mathematics, 1:269–271, 1959. [10] D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Hand- book of Computational Geometry, pages 425–461. Elsevier Science Publishers, Amster- dam, 2000.