Research Article
A Note on Computational Approach to Travelling Sales Man Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 115 - Issue 8 |
| Published: April 2015 |
| Authors: Shaik Mohiddin Shaw, Dharmaiah Gurram |
10.5120/20174-2374
|
Shaik Mohiddin Shaw, Dharmaiah Gurram . A Note on Computational Approach to Travelling Sales Man Problem. International Journal of Computer Applications. 115, 8 (April 2015), 28-33. DOI=10.5120/20174-2374
@article{ 10.5120/20174-2374,
author = { Shaik Mohiddin Shaw,Dharmaiah Gurram },
title = { A Note on Computational Approach to Travelling Sales Man Problem },
journal = { International Journal of Computer Applications },
year = { 2015 },
volume = { 115 },
number = { 8 },
pages = { 28-33 },
doi = { 10.5120/20174-2374 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2015
%A Shaik Mohiddin Shaw
%A Dharmaiah Gurram
%T A Note on Computational Approach to Travelling Sales Man Problem%T
%J International Journal of Computer Applications
%V 115
%N 8
%P 28-33
%R 10.5120/20174-2374
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Many real life situations for which there are no optimization algorithms which can solve polynomial time problems in the worst case. So researchers are trying for new approximation algorithms for such kinds of situations. Approximation algorithms give the solution which is close to the optimal solution of a particular situation. Traveling Salesman Problem (TSP) is a typical NP complete problem which lacks polynomial time algorithm. In this paper it is proposed an edge removal algorithm, which will give the nearly optimal solution within a limited time.
References
- A. V. Aho, J. E. Hopcroft and J. D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974.
- E. Horowitz and S. Sahni, "Fundamental of Computer Algorithms" , Computer Science Press, 1982.
- E. L. Lawler, J. K. Lenstra, A. RinnooyKan, and D. B. Shmoys. The TravelingSalesman Problem: A Guided Tour of Combinatorial Optimization. Wiley,Chichester, England, 1985.
- Goldberg David E, Lingle R Jr. "Alleles, Loci, and the Traveling Salesman Problem. " Proc. Of 1st Int. Conf. on Genetic Algorithms and Their Applications, Lawrence Erlbaum Associates, 1985,154-159
- E. L. Lawler, J. K. Lenstra, A. RinnooyKan, and D. B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester, England, 1985.
- A. Gibbons and W. Rytter, "Efficient Parallel Algorithms" Cambridge University Press, 1988.
- M. Weiss, "Data Structures and Algorithm Analysis", Benjamin-Cummings, 1992.
- U. Manber, "Introduction to Algorithms: A Creative approach", Addison-Wesley, 1989.
- G. Gonnet and R. Baeza-Yates, "Handbook of Algorithms and Data Structures" , Addison- Wesley, 2 ed. , 1991.
- B. Salzberg, "File Structures: An Analytic Approach", Prentice-Hall, 1988.
- C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1–11, 1993.
- S. O. Krumke, W. E. de Paepe, D. Poensgen, and L. Stougie. News from the online traveling repairman. In J. Sgall, A. Pultr, and P. Kolman, editors, Proc. 26th Symp. on Mathematical Foundations of Computer Science, volume 2136 of Lecture Notes in Computer Science, pages 487–499. Springer-Verlag, 2001.
- Prof. Lenore Cowen, Scribe: Stephanie Tauber, Lecture notes on "The Travelling Salesman Problem (TSP)", Comp260: Advanced Algorithms, Tufts University, Spring 2002.
- G. Gutin and A. P. Punnen, editors. The Traveling Salesman Problem and itsVariations. Kluwer, Dordrecht, TheNederlands, 2002.
- M. Lipmann. On-Line Routing. PhD thesis, Eindhoven University of Technology, 2003.
- K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar. Paths, trees, and minimum latency tours. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science, Cambridge, Massachusetts, 2003.
- C. Chekuri and A. Kumar. Maximum Coverage Problem with Group Budget Constraints and Applications. Proc. Of APPROX-RANDOM, LNCS, 72–83, 2004.
- C. Chekuri and M. Pal. A Recursive Greedy Algorithm for Walks in Directed Graphs. Proc. of IEEE FOCS, 245–253, 2005.
- C. Chekuri and M. Pal. An O(log n) Approximation for the Asymmetric Traveling Salesman Path Problem. Proc. of APPROX, 95–103, 2005.
- K. Chen and S. Har-Peled. The Orienteering Problem in the Plane Revisited. Proc. of ACM SoCG, 247–254, 2006.
- V. Nagarajan and R. Ravi. Poly- logarithmic approximation algorithms for Directed Vehicle Routing Problems. Proc. of APPROX, 257–270, 2007.
Index Terms
Keywords