期刊名称：International Journal of Computer Science & Technology
印刷版ISSN：2229-4333
电子版ISSN：0976-8491
出版年度：2010
卷号：1
期号：1
出版社：Ayushmaan Technologies
摘要：There are large numbers of real life problems for which there is no any optimization algorithm which can solve such kinds of problems in the polynomial time in the worst case. So researchers are designing new approximation algorithms for such kinds of problems. Approximation algorithms gives the solution which is close to the optimal solution of a particular problem. In this paper, a study on Traveling Salesman problem is being done along with the difference in the time complexities of approximation algorithm as given by different researchers and an approximation algorithm is designed for traveling salesman problem. After analysis of time complexities of approximation algorithms, it is found that Researchers are continuously applying their best efforts to design new approximation algorithms which have less time complexity and space complexity as compared to the previously existing algorithms.
