Change search
ReferencesLink to record
Permanent link

Direct link
Tolerance-based algorithms for the traveling salesman problem
P&QM Area, IIM Ahmedabad, India.
Faculty of Economic Sciences, University of Groningen, The Netherlands.
Department of Computer Science, Royal Holloway University of London, UK and Department of Computer Science, University of Haifa, Israel.
Computer Science Institute, University of Halle-Wittenberg, Germany.
2008 (English)In: Mathematical Programming and Game Theory for Decision Making / [ed] S.K. Neogy, R.B. Bapat, A.K. Das, and T. Parthasarathy, New Jersey: World Scientific, 2008, 47-59 p.Chapter in book (Refereed)
Abstract [en]

Most research on algorithms for combinatorial optimization use the costs of the elements in the ground set for making decisions about the solutions that the algorithms would output. For traveling salesman problems, this implies that algorithms generally use arc lengths to decide on whether an arc is included in a partial solution or not. In this paper we study the eect of using element tolerances for making these decisions. We choose the traveling salesman problem as a model combinatorial optimization problem and propose several greedy algorithms for it based on tolerances. We report extensive computational experiments on benchmark instances that clearly demonstrate that our tolerance-based algorithms outperform their weight-based counterpart. This indicates that the potential for using tolerance-based algorithms for various optimization problems is high and motivates further investigation of the approach.

Place, publisher, year, edition, pages
New Jersey: World Scientific, 2008. 47-59 p.
Keyword [en]
Traveling salesman problems, greedy algorithms, arc tolerances
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-83133ISBN: 9812813217OAI: diva2:665037
Available from: 2013-11-18 Created: 2013-11-18 Last updated: 2013-11-19Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Jäger, Gerold
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link