Validation of the Improved Incremental Assignment Algorithm.

Pinzhi Wang; Youssou Gningue; Haibin Zhu

The Assignment Problem is a basic combinatorial optimization problem. In a weighted bipartite graph, the Assignment Problem is to find the largest sum of weights matching. The Hungarian method is a well-known algorithm, which is combinatorial optimization. Adding a new row and a new column to a weighted bipartite graph is called the Incremental Assignment Problem (IAP). The algorithm of the Incremental Assignment Problem utilizes the given optimal solution (the maximum weighted matching) and the dual variables to solve the matrix after extending the bipartite graph. This paper proposes an improvement of the Incremental Assignment Algorithm (IAA), named the Improved Incremental Assignment Algorithm (IIAA). The improved algorithm will save the operation time and operation space to find the optimal solution (the maximum weighted matching) of the bipartite graph.

COMBINATORIAL optimization; BIPARTITE graphs

International Journal for Computers & Their Applications, 2021, Vol 28, Issue 3, p132

1076-5204

Academic Journal