Mein Buch "Toleranzen in Helsgauns Lin-Kernighan-Heuristik für das TSP" ist nun beim VDM Verlag Dr. Müller erschienen. Es handelt sich um einen Nachdruck meiner Diplomarbeit in einer überarbeiteten und korrigierten Fassung (ISBN 3836494744).

Link bei Amazon: hier.

Inhaltsverzeichnis

• Einführende Erläuterungen
  • Motivation und Vorbemerkungen
  • Das Problem des Handelsreisenden und Varianten
  • Probleminstanzen und Bezugsquellen
  • Transformation von Problemen
• TSP-Heuristiken
  • Klassen von Algorithmen
  • Lokale Suche
    • Swaps bzw. Opts
    • Einfache lokale Suche
    • Wiederholte lokale Suche und Mehrfachstart
    • Komplexität lokaler Suche
  • Klassisches Verfahren von Lin und Kerninghan
    • Kriterien bei der Suche nach k-Swaps
    • Weitere Verbesserungen
  • Modifikationen von Keld Helsgaun
    • Untere Schranke für STSP nach Held und Karp
    • Bestimmung der 1-Baum Toleranz
    • Weitere Modifikationen
    • Anfangstouren
• Toleranzen und Variationen
  • Toleranz bezüglich optimaler Touren
  • Klassifizierung von Toleranzen
  • Verwendete Ressourcen
  • Untersuchte Toleranzen und Variationen
    • Experimentiergrundlage und Einfluss der 1-Baum-Toleranz (SNN vs SLKH)
    • SRX
    • SMTE
    • SMTESOX
    • SSP3AX
    • SSP*AX
    • D2OPT
    • SLAP
    • SLKHDBLBXK(ADJ)(B)
    • SBBXPLKHYT
    • SBBTXPLKHYT
  • Vorhersagequalität statischer Toleranzen
  • Tourqualität und Laufzeit bester Versionen
  • Analysen für VLSI-Beispiele
• Weitere Untersuchungen und Modifikationen
  • MaxMatrixDimension
  • Profiler-Analyse
  • Anfangstouren -- SMTEXPI
• Abschlussbemerkungen
  • Zusammenfassung
  • Ausblick
• Anhang: Tools zur Automatisierung
  • 2collections2excel
  • Best2tex
  • Clear_collection
  • Collcetion2tex
  • ExtractResults4Vgl + GenerateVgl
  • Get_tour_length
  • Import_log2collection
  • Trials2excel + GenerateCharts
• Anhang: Spezifikation des Dateiformats Kollektion
• Literatur
• Abbildungsverzeichnis
• Listings