Bipartite Matching, Framework and Solutions

To access the theoretical document, please click [PDF]
To access the presentation, please click [Slides]

Document with 70 pages of theory and a presentation in fulfilment of the course Algorithms@Bocconi. Expanded devolving time to the Visiting Student initiative. Final grade 30/30

Abstract

In a scenario of tasks and agents that could perform them at a specified cost, the Assignment Problem aims to find the best pairs that attain an optimal cost. Such a question is very common across industries, especially with scarcity of resources, and an efficient solution is of paramount importance. It is also theoretically linked with its unweighted version, commonly referred to as Bipartite Matching, thanks to which the conditions for a solution can be identified.
First, the problem is presented from a mathematical perspective. In the second chapter, properties from the graph theory and linear algebra spectrum are proposed, highlighting a meeting point of the two subjects. Lastly, a solution through the Hungarian Algorithm by Kuhn is analyzed and justified using prior results. The whole reasoning process is backed by formal justification, with proofs and a clear set of defined objects.
Two additional chapters provide extensions in the direction of different optimization processes and magnitude of the solutions in the problem space. The former is a generalization of the proposed framework. The latter is an overview on the number of such feasible solutions in the unweighted case for a quite general type of graph.