2
$\begingroup$

Suppose n students have preferences over n different notebooks. Their preferences can be represented with a square matrix of size n where each column is a different permutation of the vector [1:n], where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.

For example, such allocation in the problem below

1 2 2

2 1 3

3 3 1

would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.

My question is the following. If the matrix with preferences is chosen uniformly at random, what is the expected maximum ranking in the assignment that minimizes the sum of rankings? In the example above, this is 2. I am interested in the maximum value that occurs in expectation if one of the possible matrices is chosen uniformly at random.

Simulations show that for n=100, this is 6.44 and for n=200 this is 7.04.

See Expected behavior of an algorithm to minimize rankings for further details.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Frieze and Sorkin showed that in the optimal solution of the assignment problem with weights chosen uniformly in $[0,1]$, the maximal value is $\Theta\bigl(\frac{\log n}{n}\bigr)$.

This suggests that the answer in your case is $\Theta(\log n)$.

I found this reference in the survey of Krokhmal and Pardalos mentioned in my answer to your original question. I suggest consulting the survey on your own for any further questions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am trying to formalize this argument. My idea is the following -> the maximal value for the problem with costs uniformly distributed in $[0,n+1]$ is $\Theta \log(n+1)$, which must be higher than the maximal value with the costs being random permutations of $[0,n]$. Does that argument sound reasonable? $\endgroup$
    – fox
    Commented Apr 4, 2022 at 15:11
  • $\begingroup$ This only gives a bound in one direction. Also, I'm not sure how the comparison that you suggest would work. $\endgroup$
    – Yuval Filmus
    Commented Apr 4, 2022 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.