Academic Awards 2024 booklet

13 Cyclic disjointness of Hamiltonian tours One of the most famous problems in the field of combinatorial optimization is the Traveling Salesman Problem, where a traveling salesman wants to finds the shortest route that visits all cities in a network exactly once and returns to his origin city. Such a route visiting all points is also called a Hamiltonian tour or cycle. This problem clearly has applications in logistics, but appears in many other areas. Translating real-world problems into such mathematical models is often hard. Some constraints or objectives cannot be precisely specified, or might make a problem (mathematically) too hard to solve. In such a setting, it is advantageous to not only find the best solution for a model, but multiple good solutions, of which a decision maker can choose the most preferred one. However, these solutions need to be somewhat diverse to offer meaningful alternatives, and a measure is needed for how distinct solutions are. Combining these concepts, in my thesis I investigated a new notion of distinctness between Hamiltonian tours, namely cyclic disjointness: the distance between any two cities in one tour must be different to their distance in the second tour. I showed that it is not always possible to find two cyclic disjoint tours. This existence result followed from a surprising relation to a completely different mathematical problem, the n-queens problem on a chessboard. 1 2 3 4 5 6 7 a: Two cyclic disjoint tours in K 7 . 1 2 3 4 5 6 7 8 9 10 11 b: Two cyclic disjoint tours in K 11 . 1 2 3 4 5 6 7 8 9 c: Two edge -disjoint tours in K 9 , which are not cyclic disjoint: for example vertices 2 and 5 have distance 3 in both tours. 1 2 3 4 5 6 7 8 9 10 11 12 13 d: Two cyclic disjoint tours in K 13 . 1 2 3 4 5 6 7 8 9 10 11 12 13 e: Two different cyclic disjoint tours in K 13 . 1 1 2 3 4 5 6 7 2 3 4 5 6 7 Q Q Q Q Q Q Q 1 1 2 3 4 5 6 7 2 3 4 5 6 7 Q Q Q Q Q Q Q 1 1 2 3 4 5 6 7 2 3 4 5 6 7 Q Q Q Q Q Q Q 1 2 3 4 5 6 7