In this thesis the travelling politician problem will be introduced. The travelling politician problem is based on the travelling salesman problem which describes the task to find the shortest tour connecting all cities when given a list of cities and their pairwise distance. The travelling politician problem represents the election campaign and the tour associated with it of a politician. In contrast to the travelling salesman problem not every city must be visited because voters travel from nearby cities to listen to speeches.
Furthermore an approximation algorithm will be developed and implemented in Java, its approximation ratio will be proven for different scenarios and it will then be studied empirically and compared to an exact algorithm, which will be implemented using an integer linear programming solver, in regard to the average quality of the approximation and its relative runtime. A separate test run will be made to test the limits of the approximation algorithm in regard to the input size.
Both the approximation algorithm and the exact algorithm will be fed with randomly generated data.
