The "electricity packing" problem

Question

The question is inspired by this paper. 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.

Is anything known about this problem?

Answer 1

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.