Please use this identifier to cite or link to this item: https://zone.biblio.laurentian.ca/handle/10219/3387
Title: Improving group role assignment problem by incremental assignment algorithm
Authors: Wang, Pinzhi
Keywords: assignment problem;weighted bipartite graph;Hungarian algorithm;incremental assignment problem;improved incremental assignment algorithm;group role assignment
Issue Date: 29-Oct-2019
Abstract: The Assignment Problem is a basic combinatorial optimization problem. In a weighted bipartite graph, the Assignment Problem is to find a 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 maximum weighted matching (the optimal solution) of the weighted bipartite graph has been given. 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 extended bipartite graph. This thesis proposes an improvement of the Incremental Assignment Algorithm (IAA), named the Improved Incremental Assignment Algorithm. The improved algorithm will save the operation time and operation space to find the optimal solution (the maximum weighted matching) of the bipartite graph. We also present the definition of the Incremental Group Role Assignment Problem that based on the Group Role Assignment Problem (GRAP) and Incremental Assignment Problem (IAP). A solution has been designed to solve it by using the Improved Incremental Assignment Algorithm (IIAA). In this thesis, simulation results are presented. We utilize the tests to compare the algorithm of the Incremental Assignment Problem and the Improved Incremental Assignment Algorithm (IIAA) to show the advantages of IIAA.
URI: https://zone.biblio.laurentian.ca/handle/10219/3387
Appears in Collections:Computational Sciences - Master's theses
Master's Theses

Files in This Item:
File Description SizeFormat 
Thesis-MSc-Pinzhi.pdf1.53 MBAdobe PDFThumbnail
View/Open


Items in LU|ZONE|UL are protected by copyright, with all rights reserved, unless otherwise indicated.