On the number of $k$-cycles in the assignment problem for random matrices

Details On the number of $k$-cycles in the assignment problem for random matrices On the number of $k$-cycles in the assignment problem for random matrices

2008-03-28

arxiv.org/abs/0803.4096v1

Computer Science

Discrete Mathematics

To appear in Journal of Statistical Mechanics

Scientific paper

10.1088/1742-5468/2008/03/P03019

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 one and two-cycles are dominant in the optimal solution. In the antisymmetric case the situation is the opposite and the one and two-cycles are suppressed. We solve the model for a pure random matrix (without correlations between its entries) and give analytic arguments to explain the numerical results in the symmetric and antisymmetric case. 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 one and two cycles.

Affiliated with

Also associated with

No associations

Rating

On the number of $k$-cycles in the assignment problem for random matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the number of $k$-cycles in the assignment problem for random matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of $k$-cycles in the assignment problem for random matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-173875