Der Achatz-Kleinschmidt-Paparrizos-Algorithmus, auch AKP-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse kann als Spezialfall der linearen Optimierung formuliert werden. Der AKP-Algorithmus ist besonders für dünne Graphen geeignet. Seine Komplexität des Algorithmus beträgt H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem, Applied geometry and discrete mathematics, the Victor Klee Festschrift. S. 5.
Der Algorithmus wurde 1991 von Hans Achatz, Peter Kleinschmidt und Konstantinos Paparrizos veröffentlicht.H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem, Applied geometry and discrete mathematics, the Victor Klee Festschrift. S. 1.
Literatur H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem, Applied geometry and discrete mathematics, the Victor Klee Festschrift. S. 1–11.
Einzelnachweise
Kategorie:Lineare Optimierung Kategorie:Algorithmus