A NOVEL GRAPH THEORY TECHNIQUE TO SOLVE ASSIGNMENT PROBLEMS

Abstract

The Assignment Problem (AP) is a mathematical optimization problem that has to do with allocating resources to projects in the best possible way. Subject to limitations like resource availability or task requirements, the goal is to identify the assignment that minimizes costs or maximizes benefits. The Minimum Spanning Tree (MST), on the other hand, is a graph theory idea that focuses on identifying the tree that, among all potential trees, connects all of the vertices in a graph, and has the lowest overall weight. To address APareas this study suggested a novel method that makes use of the MST technique. The assignment problem is first represented by the method as a weighted graph, where the resources and tasks are represented by the vertices, and the costs of allocating a resource to a task are represented by the edges. Based on these costs, the edge weights are determined. A weighted graph is then used by the technique to generate an MST. This is accomplished by using an appropriate MST algorithm, such as Kruskal’s or Prim’s algorithm. The resulting MSTrepresentsthe best distribution of resources among tasks to reduce overall expenditure. To ensure that all tasks are assigned and the overall cost is kept to a minimum, each edge in the MST corresponds to the assignment of a resource to a job. Compare the proposed algorithm’s performance to that of the Hungarian Method, an established technique for resolving APs to confirm its efficacy. We provide a thorough analysis utilizing numerous benchmark assignment problems and assess the solutions’ optimality. The outcomes of our comparative analysis show that the Hungarian Method and our suggested algorithm both produce the best results. This suggests that using the MST technique offers an alternative methodfor resolving APs. By researching and exhibiting the potential of MSTs to effectively and efficiently address APs