Hello everyone, I hope you all are doing well.

I wanted to post a question, which I am unable to solve. I even gave that problem to some of my CM friends and yet it remains unsolved. Hence, I thought it is a good time to put it up on the community :). So the question goes like this:

There are N Base-Stations (BS) and P users. jth BS allocates Cj resources per packet. If the user i connects to BS j, he gets Rij number of packets. User, i can connect to a limited set of BS given by the set Ui.

All the entries of Cj, Rij are non-negative. You know the vector {Cj} (1<=j<=N), 2D-matrix {Rij} (1<=j<=N,1<=i<=P), set of sets {Ui}.(You can basically remove the importance of Ui's completely by tweaking the Rij matrix as explained below)(Please see the example for more clarification)

You need to allocate all the users to exactly one BS of their own. (Please see the example for more clarification). You need to find an allocation such that, the sum of average resource allocated by a base station to its users over all BS, is maximized. More formally, you need to find an allocation that maximizes ΣΣ((Cj*Rij*Iij)/Nj); Where the 1st sum is over j and the inner sum is over i. Note that Iij = 1 if User i is connected to BS j, Iij=0 otherwise and Nj is the number of users connected to BS j.

P.S. You can effectively remove the importance of Ui's by keeping 0 at appropriate places in Rij. Closed-form solutions will be much appreciated. An example is given below:

Ex- N=4, P=2; C = {10, 10, 10, 2} -- C1 = 10, C2 = 10, C3 = 10, C4 = 2;

R = {{2, 2, 2, 2}, {1, 1, 1, 1}} -- R11 = 2, R22 = 1 and so on

U1 = {1, 2, 3} -- means U1 can connect to BS 1, 2, or 3; U2 = {3, 4} -- means U2 can connect to BS 3, or 4

Optimal allocation is : A = {1, 3} -- U1 connects to BS 1 and U2 connects to BS 3. The value of required maximized sum = 30

Ex- N=3, P=5; C = {1, 2, 3}; R = {{1, 2, 3}, {3, 2, 1}, {1, 1, 1}, {2, 2, 2}, {3, 3, 3}}; U1 = {1}; U2 = {1,2}; U3 = {3}; U4 = {1,3}; U5 = {2}; Optimal allocation is:A = {1, 1, 3, 3, 2}, maximized sum value = 12.5;

According to me, it should be a problem of game-theory or DP but any approaches are welcome.

Once again stay safe, stay happy, stay coding :)