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?

  • $\begingroup$ 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? $\endgroup$
    – A.Omidi
    Commented Feb 21, 2021 at 12:43
  • $\begingroup$ Are you trying to prove that your problem is NP-hard (by reducing it to a known NP-hard problem)? $\endgroup$
    – prubin
    Commented Feb 21, 2021 at 16:38
  • $\begingroup$ @prubin Yes, I'm trying to prove that the problem is NP-Hard $\endgroup$
    – ephemeral
    Commented Feb 23, 2021 at 13:02


Your Answer

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