Abstract: The classic Traveling Salesperson Problem (TSP) asks one to compute a shortest tour (cycle) that visits a given set of sites (nodes) in a network. Many variations of the TSP arise in geometric settings, depending on the objective function, the constraints, and what types of "sites" are to be visited. The Euclidean TSP on a set of point sites can be approximated arbitrarily well, with a "PTAS" (polynomial-time approximation scheme). We survey some of these recent results and sketch the proof of one scheme based on "m-guillotine subdivisions".
Kolloquium - 16 Uhr s.t.
Abstract: Der Kantengraph eines Graphen G ist der Graph auf der Kantenmenge von G, in dem zwei Ecken genau dann verbunden sind, wenn sie (als Kanten) in G inzidieren. Thomassen hat vermutet, dass jeder endliche 4-zusammenhängende Kantengraph einen Hamilton-Kreis besitzt. Der Vortrag handelt von älteren und neuen Ergebnissen aus dem Umfeld dieser Vermutung.