Max-min fairness is a useful concept in communications.
A friend of mine recently wanted me to write an algorithm which can be used to select communication links with max-min fairness for multiple users. I thought it might be useful/interesting for some.
Problem: Select an element from each row of a given matrix, maximizing the minimum value (max-min fairness), under the constraint that no two elements should be from the same row.
MATLAB implementation: m-file
Example call of the function in MATLAB:
Nr = 3;
Nc = 4;
mat = abs(randn(Nr,Nc));
Y = maxminfair(mat);
Use: This is useful in problems like assigning users communication links, under a constraint that some links can be used by only a single user at a given time. Or when finding minimum cost paths for few users simultaneously, when some links in the graph can be taken by only one user at a time.
Note: The matrix passed to the function should have all elements real and positive. (It can be generalized, but I did not want it for my problem, as all the elements were energy quantities)
If the matrix you need to use has zero or negative elements, pass ‘mat – min(min(mat))+1‘ instead and add ‘min(min(mat)) – 1‘ to the final answer.
If there are any bugs in the algo, or any improvements that can/must be made, do let me know.












