On the Maximum Number of Alternative Solutions for the k-best Method and the Penalty Method

unforeseen events. The generated alternatives should be good among the target funtion and should not be too similar. Here a simple approach is to take the second best, third best or even k-best solution as the alternative one. Typically it turns out that these
alternatives are pretty similar to the optimal solution for a small k. A better strategy for generating real alternatives is the penalty method. For “Sum Type Problems“ it works as follow:
• Create an optimal solution.
• Choose a penalty parameter ε > 0.
• Multiply all weights of elements which are part of the optimal solution with the factor (1 + ε).
• Create an optimal solution for the problem with the modified weights. This solution is called ε-alternative.
Here we can control the weight of the alternative solution and the difference to the optimal solution by the choice of the penalty parameter.
It was studied by Schwarz and Sameith how good it is to have the choice among two alternatives and how the k for the k-best method or the penalty parameter ε for the penalty method should be chosen to receive two good alternatives. The quality of these alternatives was measured in different perturbation models. It turned out that
the penalty method delivers a lot better results than the k-best method.
Now we study the case that we generate all possible alternatives with the help of these two methods. How many alternatives are possible for different problems if we choose the k-best or the penalty method?
Herefore we take a look at the MST problem, the shortest path problem, the assignment problem and the TSP. It turns out that the maximum number of alternatives generated by the k-best method is exponentially in the input size. Here the penalty method again
is a lot better. We can show that the maximum number of alternative solutions lies in the complexity class Θ(n2 ) for the shortest path problem, the assignment problem and the TSP, where n is the number of vertices in the graph. For the MST problem the results are quite better, here the maximum number of alternative solutions lies in the
complexity class Θ(n).