*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 9
Dienstag, 19.09.2000, 16.30–16.50 Uhr, WIL C 133

K-Alternative versus K-Best Algorithms

Ingo Althöfer, FSU Jena, Institut Angewandte Mathematik

In a DECISION SUPPORT SYSTEM WITH MULTIPLE CHOICE STRUCTURE a computer program does not give ”the optimum”. Instead it computes a clear handful of interesting candidate solutions. Then a human (expert) has the final choice amongst these computer proposals.

Often k-best algorithms are not well suited for the generation of such candidate solutions: the k best solutions may be merely micro mutations of each other instead of true alternatives. This problem is bothering for instance in shortest path scenarii.

One possible way to generate true alternatives is the following penalty method with several rounds: First of all the best solution in the traditional sense is computed. Then certain building blocks are punished in the objective function. For the modified objective function again the best solution is computed. Certain building blocks are punished, and so on.

We present a monotonicity theorem for the penalty method which applies to all situations with sum-type objectives. Applications are discussed, concerning especially shortest paths and matchings.