Achatz-Kleinschmidt-Paparrizos algorithm

The Achatz-Kleinschmidt-Paparrizos algorithm , also known as the AKP algorithm , is an algorithm for solving weighted assignment problems on bipartite graphs . This problem class can be formulated as a special case of linear optimization . The AKP algorithm is particularly suitable for thin graphs. Its algorithm complexity is ${\ displaystyle O (n ^ {3}).}$

The algorithm was published in 1991 by Hans Achatz , Peter Kleinschmidt and Konstantinos Paparrizos .

literature

H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem , Applied geometry and discrete mathematics, the Victor Klee Festschrift. Pp. 1-11.

Individual evidence

↑ H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem , Applied geometry and discrete mathematics, the Victor Klee Festschrift. P. 5.
↑ H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem , Applied geometry and discrete mathematics, the Victor Klee Festschrift. P. 1.

[1] H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem , Applied geometry and discrete mathematics, the Victor Klee Festschrift. P. 5.

[2] H. Achatz, P. Kleinschmidt, K. Paparrizos (1991): A Dual Forest Algorithm for the Assignment Problem , Applied geometry and discrete mathematics, the Victor Klee Festschrift. P. 1.