Optimal Solution Bounds for the Random Assignment problem

The Random Assignment Problem is a significant challenge in optimization theory that involves allocating a set of n jobs to an equal number of machines to minimize total cost. The costs are assigned to each machine to complete each job and in this formulation are considered as random variables with an uniform distribution between 0 and 1. Despite its apparent simplicity, this problem has captivated mathematicians and researchers for decades. A key difficulty lies in estimating the expected value of the cost associated with the optimal solution, denoted as E[An]. Early attempts to bound this expected value resulted in orders of log n until Walkup’s result in 1979, where he demonstrated that E[An] is bounded independently of n, establishing an unexpected constant bound of 3+o(1). This result, that was grounded in graph theory and linear programming, laid the foundation for further advancements in understanding the problem and subsequent research led to the discovery of bounds for E[An] using diverse mathematical techniques. However, the most significant breakthrough occurred in 1987 when Parisi and Mézard applied concepts from statistical physics to derive a remarkable estimation for E[An]. Their work, based on the replica method and spin glass theory, suggested that as n tends to infinity, E[An] converges to (π^2)/6 , providing a surprising result that also came from a different field of research. The only aspect left to address was providing a rigorous mathematical proof instead of an estimate and the first formal demonstration of this result was presented years later by Aldous in his article “The ζ(2) Limit in the Random Assignment Problem”, which will be the main focus of this thesis. After the introductory chapter that aims to synthesize the problem’s evolution, Chapter 2 will outline the main steps of Aldous’s proof for a comprehensive understanding, and Chapter 3 will examine the details necessary to complete the demonstration. To emphasize the practical relevance of the random assignment problem, Chapter 4 will explore one of its possible applications. Specifically, it will focus on the article: “Privacy preserving wireless communication using bipartite matching in social big data” which explain how to employ a bipartite matching method to address a privacy protection issue showing the practical impact of theoretical advancements in combinatorial optimization.