umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
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 (Engelska)Ingår i: 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, s. 47-59Kapitel i bok, del av antologi (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
New Jersey: World Scientific, 2008. s. 47-59
Nyckelord [en]
Traveling salesman problems, greedy algorithms, arc tolerances
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-83133ISBN: 9812813217 (tryckt)OAI: oai:DiVA.org:umu-83133DiVA, id: diva2:665037
Tillgänglig från: 2013-11-18 Skapad: 2013-11-18 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Jäger, Gerold

Sök vidare i DiVA

Av författaren/redaktören
Jäger, Gerold
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 125 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf