AlKoP

It is presumed that problems that are shown NP-complete cannot be solved in polynomial time. Nevertheles, solutions to these problems must be found, even if they are not optimal, as long as they can be generated quickly. Besides devising such fast approximation algorithms for combinatorial optimization problems, a considerable art is to determine the quality of the obtained solution in terms of the optimum solution without knowing it. Another important aspect of an approximation algorithm is to present a bad input, a so-called witness, that is an input where the algorithm may output quite a bad feasible solution that is far away from the optimum solution. Especially in the field of the Traveling Salesperson Problem there are some heuristics in use where the gap between witnesses and performance guarantees are still considerably large. In this focus of research, we would like to design good witnesses against some of these heuristics.