On the number ofk-cycles in the assignment problem for random matrices
José G Esteve, Fernando Falceto · Journal of Statistical Mechanics Theory and Experiment · 2008
We continue the study of the assignment problem for a random cost matrix. We analyse the number of k -cycles for the solution and their dependence on the symmetry of the random matrix. We observe that for a symmetric matrix 1- and 2-cycles are dominant in the optimal solution. In the antisymmetric case the situation is the opposite and the 1- and 2-cycles are suppressed. We solve the model for a pure random matrix (without correlations between its entries) and give analytic arguments for explaining the numerical results in the symmetric and antisymmetric cases. We show that the results can be explained to great accuracy by a simple ansatz that connects the expected number of k -cycles to that of 1- and 2-cycles.