# Hardness Reduction for assigning Users to Servers

Suppose there are $$x$$ servers, and $$y$$ users. The $$y$$ users are to be assigned to the $$x$$ servers similar to classic scheduling problems. The cost of using servers is given by $$c(|x|)$$ which is an increasing function of $$x$$, the number of servers. The more the number of servers used, the higher the cost function. There is another load function $$L(x_i)$$ which indicates the load, i.e. number of users assigned to each server $$x$$. The optimization objective is to Minimize the cost function of the servers, i.e. Minimize $$c(|x|)$$ such that the load at each server is within a pre-specified limit, i.e, $$L(x_i) \leq k$$.

If we look at the solution space of the problem, it comprises an exponential number of choices representing each user-server combination as per my understanding goes. What would be a reduction to prove the Hardness of this problem if my intuition about the solution space is indeed correct?

• Your problem sounds like the generalized assignment problem (GAP) or its variant and might be solved efficiently by using the exact/heuristic method. Would you try it? Commented Feb 21, 2021 at 12:43
• Are you trying to prove that your problem is NP-hard (by reducing it to a known NP-hard problem)?
– prubin
Commented Feb 21, 2021 at 16:38
• @prubin Yes, I'm trying to prove that the problem is NP-Hard Commented Feb 23, 2021 at 13:02