3rd Colloquium of Research Area KL

Date: January 31, 2014
Venue:  Seminar room 1st floor, Arithmeum, Lennéstr. 2, Bonn


15:45 Coffee and Tee (Lounge 2nd floor, Arithmeum, Lennéstr. 2)
16:15 Stefan Hougardy: Eliminating edges in TSP instances
17:00 Coffee break
17:30 Philipp Schlicht: Computations on ordinals and automatic structures
  After the Colloquium there will be the opportunity to have dinner together


Stefan Hougardy: Eliminating edges in TSP instances

The Traveling Salesman Problem is one of the best studied NP-hard problems in combinatorial optimization. Powerful methods have been developed within the last 60 years to find optimum solutions to large TSP instances. The largest TSP instance so far that has been solved optimally has 85,900 vertices. Its solution required more than 136 years of CPU time using the branch-and-cut based Concorde TSP code of Applegate, Bixby, Chvátal,and Cook. We present results that allow to prove that some edges of a TSP instance cannot occur in any optimum TSP tour and we propose a combinatorial algorithm to identify such edges. The runtime of the main part of our algorithm is O(n^2 log n) for an n-vertex TSP instance. We are able to eliminate more than 99.993% of all edges of a 100,000 vertex TSP instancewithin four days of CPU time. Our approach allowed for the first time tofind the optimum solution to a large euclidean TSP instance. This is joint work with Rasmus Schroeder.

Philipp Schlicht: Computations on ordinals and automatic structures

Turing computations can be generalized to the ordinal numbers in various ways, for example by considering computations on a standard tape with ordinal time (infinite time Turing machines) or on an ordinal length tape with ordinal time (ordinal Turing machines). A limit function is introduced to define the transition at limit times. These machines were introduced by Hamkins, Kidder, and Koepke. There are many connections with computability and descriptive set theory, related to the classes of sets which the machines can compute. In this talk I would like to focus on automata generalized to ordinals. A motivation is that structures with a presentation by such automata have decidable first oder theories. Input words have ordinal length and the letters are read successively with a limit condition. An automatic presentation of a structure is an identification of the domain, relations and functions with regular sets of tuples of words. For example, the ordinals as linear orders with an automatic presentation are those below omega^omega. I would like to discuss results on automatic structures, ordinal automatic structures, and their relationship with tree automatic structures by Delhomme, Khoussainov, Stephan, and Kartzow, some obtained in joint work.