Online TSP

Das Online TSP ist eine Variante des Problems des Handlungsreisenden, bei dem dem Reisenden während der Fahrt 'per Handy' neue zu besuchende Zielorte mitgeteilt werden. Dieser muß die neuen Zielorte dann in seine Tour einplanen.

Inhalt des Vortrags:

• genaue Vorstellung des Problems
• untere Schranke mit Beweis (Theorem 3.1)
• Strategie PAH
• Kompetitivität der Strategie mit Beweis (Therorem 4.1)

Literatur:

Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, Maurizio Talamo. Competitive Algorithms for the On-line Traveling Salesman in: Proc. 4th Workshop Algorithms Data Struct. Springer-Verlag, 1995.

Betreuer:
Thomas Kamphans