*Wissenschaftliches Programm* *Liste der Vortragenden*

**Sektion 9**

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

#### 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.