Approximation performance of ant colony optimization for the TSP(1,2) problem

References

• E. Angel, A survey of approximation results for local search algorithms, Efficient Approximation and Online Algorithms, Lecture Notes in Computer Science, Vol. 3484, (2006), pp 30–73.
   Google Scholar
• B. Doerr and D. Johannsen, Refined runtime analysis of a basic ant colony optimization algorithm, Proceedings of the IEEE Congress on Evolutionary Computation, D. Srinivasan, and L. Wang, eds., IEEE Press, Piscataway, NJ, 2007, pp. 501–507.
   Google Scholar
• B. Doerr, F. Neumann, D. Sudholt, and C. Witt, On the runtime analysis of the 1-ANT ACO algorithm, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Hod Lipson, eds., ACM, London, 2007, pp. 33–40.
   Google Scholar
• W.J. Gutjahr, First steps to the runtime complexity analysis of ant colony optimization, Comput. Oper. Res. 35(9) (2008), pp. 2711–2727. doi: 10.1016/j.cor.2006.12.017
   Web of Science ®Google Scholar
• W. J. Gutjahr and G. Sebastiani, Runtime analysis of ant colony optimization with best-so-far reinforcement, Methodology Comput. Appl. Probab. 10(3) (2008), pp. 409–433. doi: 10.1007/s11009-007-9047-1
   Web of Science ®Google Scholar
• C. Horoba and D. Sudholt, Running time analysis of ACO systems for shortest path problem, In T.Stützle. M. Birattari, and H. H. Hoos, editors, SLS volume 5752 of Lecture Notes in Computer Science, Springer, Brussels, 2009, pp.76–91.
   Google Scholar
• R. M. Karp, Reducibility Among Combinatorial Problems, Pluner, New York, 1972.
   Google Scholar
• S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, On syntactic versus computational views of approximability, Proceedings 35th Annual IEEE Symposium on Foundations of Computer Science, Sante Fe, 1994, pp 819–836.
   Google Scholar
• T. Kötzing, P. K. Lehre, F. Neumann, and P. S. Oliveto, Ant colony optimization and the minimum cut problem, GECCO '10 Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, Portland, 2010, pp. 1393–1400.
   Google Scholar
• T. Kötzing, F. Neumann, D. Sudholt, and M. Wagner, Simple Max-Min ant systems and the optimization of linear pseudo-Boolean functions. Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA 2011), Hans-Georg Beyer, and William B. Langdon, eds., ACM, New York, 2011, pp. 209–218.
   Google Scholar
• T. Kötzing, F. Neumann, and H. Roglin, Theoretical analysis of two ACO approaches for the traveling salesman problem, Swarm Intell 6 (2012), pp. 1–21. doi: 10.1007/s11721-011-0059-7
   Web of Science ®Google Scholar
• S. Lin and B.W. Kernighan, Efficient heuristic algorithm for the traveling salesman problem, Oper. Res. 21(2) (1973), pp. 498–516. doi: 10.1287/opre.21.2.498
   Web of Science ®Google Scholar
• F. Neumann, D. Sudholt, and C. Witt, Analysis of different MMAS ACO algorithms on unimodal functions and plateaus, Swarm Intell. 3(1) (2009), pp. 35–68. doi: 10.1007/s11721-008-0023-3
   Google Scholar
• F. Neumann and C. Witt, Runtime analysis of a simple ant colony optimization algorithm, In Proceedings of the 17th International Symposium Algorithms Computation (ISAAC), LNCS, Vol. 4288. Kolkata: Springer-Verlag, December 2006, pp. 618–627.
   Google Scholar
• F. Neumann and C. Witt, Ant colony optimization and the minimum spanning tree problem, In Proceeding of the Learning and the Intelligent Optimization – LION 2, LNCS Vol. 5313, Berlin: Springer-Verlag, Preliminary version: Electron. Colloq. Comput. Complexity (ECCC), Rep. 143 (2008), pp. 153–166.
   Google Scholar
• C. H. Papadimitriou and M. Yannakakis, The traveling salesman problem with distances one and two, Math. Oper. Res 18(1) (1993), pp. 1–11. doi: 10.1287/moor.18.1.1
   Web of Science ®Google Scholar
• S. Sahni and T. Gonzales, P-complete approximation problems, J.ACM 23 (1976), pp. 555–565. doi: 10.1145/321958.321975
   Web of Science ®Google Scholar
• Y. Zhou, Runtime analysis of an ant colony optimization algorithm for TSP instances, IEEE Trans Evolut. Comput. 13(5) (2009), pp. 1083–1092. doi: 10.1109/TEVC.2009.2016570
   Web of Science ®Google Scholar