# The "electricity packing" problem

In a distant village, there are $$n$$ electricity consumers. Consumer $$i$$ has a power demand of $$d_i$$ watts. The total electricity supply is $$s$$ watts. If $$s\geq \sum_{i=1}^n d_i$$, then all consumers are connected all the time. But if this is not the case, then we would like to find the largest fraction $$r\in[0,1]$$ such that it is possible to connect all consumers at least $$r$$ of the time.

Here are some examples for $$n=3$$ consumers and $$s=3$$ watts, for different demand vectors:

• $$(1,1,1)$$: $$r=1$$. We can connect all consumers in parallel all the time.
• $$(2,2,2)$$: $$r=1/3$$. We must connect the consumers in sequence, so the best we can do is connect each consumer one third of the time.
• $$(2,2,1)$$: $$r=1/2$$. We can connect the two large consumers in sequence, each of them $$1/2$$ of the time, and connect the small consumer in parallel to them.
• $$(2,1,1)$$: $$r=2/3$$. We can connect the large consumer in time $$[0,2/3)$$, the second consumer in time $$[0,1/3)\cup [2/3,1]$$, and the third one in time $$[1/3,1]$$. Note that in each time the total consumption is at most $$3$$.

Two somewhat related problems are:

• Bin packing. If the demands can be packed into $$k$$ bins of size $$s$$, then $$r\geq 1/k$$. But it is not tight, as shown by the example $$(2,1,1)$$ above.
• Parallel task scheduling. This problem involves tasks with "length" and "width". The width is analogous to the demand in our problem, and the length is somewhat related to $$r$$. But I did not find a variant in which this $$r$$ should be maximized.

Here is an elaboration of my comment. From what I can understand, the OPs problem can be cast as the solution of a large implicit linear program. Given the $$n$$ numbers $$d_1,d_2,\ldots,d_n$$ let $$\mathcal{S}$$ denote the set of subsets of $$[n]$$ such that $$S \in \mathcal{S}$$ iff $$\sum_{i \in S} d_i \le s$$. These are the feasible customer sets at any given time. We can normalize time to be one unit. If $$S_t \in \mathcal{S}$$ is the feasible set served at time $$t$$ then the total fraction of time that an element $$i$$ is served is $$\int_{0}^1 [i \in S_t] dt$$. We want to find $$r$$ such that $$\min_i \int_{0}^1 [i \in S_t] dt \ge r$$. We can write this as an LP with variables $$x_S, S \in \mathcal{S}$$ to denote the total time in $$[0,1]$$ that $$S$$ is used for. $$\begin{eqnarray*} \max r && \\ \sum_{S \in \mathcal{S}} x_S & \le & 1 \\ \sum_{S \ni i} x_S & \ge & r \quad \text{for all i}\\ x & \ge 0\end{eqnarray*}$$ & One can write the dual of this LP $$\begin{eqnarray*} \min \alpha && \\ \sum_{i} \beta_i & \ge & 1 \\ \alpha - \sum_{i \in S} \beta_i & \ge & 0\quad \text{for all S \in \mathcal{S}} \\ \alpha, \beta, \ge 0\end{eqnarray*}$$ One can see that the separation oracle for the dual corresponds to the Knapsack problem: given $$\beta_i$$ values, find the set $$S \in \mathcal{S}$$ that maximizes $$\beta(S)$$. Hence, via the FPTAS for Knapsack, one should be able to use Ellipsoid and obtain a $$(1-\epsilon)$$-approximation to the dual and hence the primal as well.
Now for NP-Hardness. Suppose we have a 2-Partition instance with numbers $$d_1,d_2,\ldots, d_n$$. Recall that we want to know if there is a partition of the numbers into two sets such that the sum of numbers in each part is exactly $$(\sum_i d_i)/2$$. We can reduce the 2-Partition problem to the OPs problem by setting $$s = (\sum_i d_i)/2$$. The claim is that $$r=1/2$$ is achievable iff the answer to the original 2-Partition problem is YES.
• Thanks! Just to elaborate on the last claim: if there exists an exact 2-partition, then by connecting each of the two subsets $1/2$ of the time, $r=1/2$ is attained. Conversely, if $r=1/2$ is possible then the total supply used is $\sum_i d_i / 2$, which is exactly $s$. Therefore, at each time, all the supply must be used. Take an arbitrary time $t$ and consider the set of consumers connected at $t$; this set and its complement are a solution to 2-partition. Jun 29 at 4:47