We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Validation of the Improved Incremental Assignment Algorithm.
- Authors
Pinzhi Wang; Youssou Gningue; Haibin Zhu
- Abstract
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.
- Subjects
COMBINATORIAL optimization; BIPARTITE graphs
- Publication
International Journal for Computers & Their Applications, 2021, Vol 28, Issue 3, p132
- ISSN
1076-5204
- Publication type
Academic Journal