I am tring to prove the NP-completeness of the following Binary Integer Linear Program (BILP):

$$ \text{min}\sum_i\sum_j x_{ij}\\ \text{subject to} \sum_jr_{ij}x_{ij} \geq R,\ \ \forall \ \ i \in [L]\\ \sum_i x_{ij} \leq 1,\ \ \forall \ \ j \in [N]\\ x_{ij} \in \{0,1\}.$$

This a resource allocation problem in which I am trying to minimize the number of resources utilized while guaranteeing a certain minimum rate for all entities.

$x_{ij}$ is an indicator random variable that indicates whether or not a resource $j$ is allocated to an entity $i$. The first set of constraints impose a minimum amount of resource guaranteed for each entity. $r_{ij}$ is the rate that an entity $i$ can get in a resource element $j$. The second set of constraints ensure that a resource is not allocated to multiple users as sharing of resources is not possible in this problem. $[L]$ is the set of user entities and $[N]$ is the set of resources here.

I have tried looking at several covering problems like set cover that look like this but the second set of constraints seem to be falling out of place every time. Can anyone suggest an existing NP complete problem that can be reduced to this problem to prove it's NP-completeness?



If you set $N = 2$, and $r_{i0} = r_{i1} = r_i$ for each $i$, and set $R = \frac12 \sum_{i \in [L]} r_i$, then the feasibility of this linear program is precisely the Partition problem. Namely, a feasible solution chooses for each $i \in [L]$ either $x_{i0}$ or $x_{i1}$, so that summing the $r_i$ for those $i$ for which you chose $x_{i0}$ equals $R$, and similarly for $1$.

  • $\begingroup$ Hi Mees It looks familiar to the partition problem for a small value of $N$ but the major difference between the two is the minimization in my optimization function. The partition problem exhausts the entire set every time whereas I am trying to minimize the sum of $x_{ij}$'s. That seems to make the two problems fundamentally different in my opinion. $\endgroup$
    – S.Zuhra
    May 18 '17 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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