<p>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 <span class="math-container">$n$</span> numbers <span class="math-container">$d_1,d_2,\ldots,d_n$</span> let <span class="math-container">$\mathcal{S}$</span> denote the set of subsets of <span class="math-container">$[n]$</span> such that <span class="math-container">$S \in \mathcal{S}$</span> iff <span class="math-container">$\sum_{i \in S} d_i \le s$</span>. These are the feasible customer sets at any given time. We can normalize time to be one unit. If <span class="math-container">$S_t \in \mathcal{S}$</span> is the feasible set served at time <span class="math-container">$t$</span> then the total fraction of time that an element <span class="math-container">$i$</span> is served is <span class="math-container">$\int_{0}^1 [i \in S_t] dt$</span>. We want to find <span class="math-container">$r$</span> such that <span class="math-container">$\min_i \int_{0}^1 [i \in S_t] dt \ge r$</span>. We can write this as an LP with variables <span class="math-container">$x_S, S \in \mathcal{S}$</span> to denote the total time in <span class="math-container">$[0,1]$</span> that <span class="math-container">$S$</span> is used for.
<span class="math-container">\begin{eqnarray*} \max r &amp;&amp; \\ \sum_{S \in \mathcal{S}} x_S &amp; \le &amp; 1 
 \\ \sum_{S \ni i} x_S &amp; \ge &amp; r \quad \text{for all $i$}\\ x &amp; \ge 0\end{eqnarray*}</span> &amp;
One can write the dual of this LP
<span class="math-container">\begin{eqnarray*} \min \alpha &amp;&amp; \\ \sum_{i} \beta_i &amp; \ge &amp; 1 
 \\ \alpha - \sum_{i \in S} \beta_i &amp; \ge &amp; 0\quad \text{for all $S \in \mathcal{S}$} \\ \alpha, \beta, \ge 0\end{eqnarray*}</span>
One can see that the separation oracle for the dual corresponds to the Knapsack problem: given <span class="math-container">$\beta_i$</span> values, find the set <span class="math-container">$S \in \mathcal{S}$</span> that maximizes <span class="math-container">$\beta(S)$</span>. Hence, via the FPTAS for Knapsack, one should be able to use Ellipsoid and obtain a <span class="math-container">$(1-\epsilon)$</span>-approximation to the dual and hence the primal as well.</p>
<p>Now for NP-Hardness. Suppose we have a 2-Partition instance with numbers <span class="math-container">$d_1,d_2,\ldots, d_n$</span>. 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 <span class="math-container">$(\sum_i d_i)/2$</span>. We can reduce the 2-Partition problem to the OPs problem by setting <span class="math-container">$s = (\sum_i d_i)/2$</span>. The claim is that <span class="math-container">$r=1/2$</span> is achievable iff the answer to the original 2-Partition problem is YES.</p>

CC BY-SA 4.0
2021-06-29T04:47:52.443Z
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.
Erel Segal-Halevi
CC BY-SA 4.0
2021-06-29T07:55:27.933Z
Since there is an FPTAS, there should not be an analogous reduction from 3-partition (unless P=NP). But so far I could not find where exactly it fails.
Erel Segal-Halevi
CC BY-SA 4.0
2021-06-29T21:06:18.223Z
@ErelSegal-Halevi Yes, good question re 3-partition. It does seem to be the case the the 3-partition can be reduced in a similar fashion. However, I wasn't sure if an FPTAS for approximating r implies an exact algorithm for 3-Partition. It seems to be connected to the fact that we do have an asymptotic FPTAS for Bin Packing.
Chandra Chekuri
CC BY-SA 4.0
2021-06-27T21:02:46.083Z
2021-06-27T21:02:46.083Z
Chandra Chekuri
<p>The question is inspired by <a href="https://link.springer.com/article/10.1007/s10458-019-09428-8" rel="nofollow noreferrer">this paper</a>.
In a distant village, there are <span class="math-container">$n$</span> electricity consumers. Consumer <span class="math-container">$i$</span> has a power demand of <span class="math-container">$d_i$</span> watts. The total electricity supply is <span class="math-container">$s$</span> watts. If <span class="math-container">$s\geq \sum_{i=1}^n d_i$</span>, then all consumers are connected all the time. But if this is not the case, then we would like to find the largest fraction <span class="math-container">$r\in[0,1]$</span> such that it is possible to connect all consumers at least <span class="math-container">$r$</span> of the time.</p>
<p>Here are some examples for <span class="math-container">$n=3$</span> consumers and <span class="math-container">$s=3$</span> watts, for different demand vectors:</p>
<ul>
<li><span class="math-container">$(1,1,1)$</span>: <span class="math-container">$r=1$</span>. We can connect all consumers in parallel all the time.</li>
<li><span class="math-container">$(2,2,2)$</span>: <span class="math-container">$r=1/3$</span>. We must connect the consumers in sequence, so the best we can do is connect each consumer one third of the time.</li>
<li><span class="math-container">$(2,2,1)$</span>: <span class="math-container">$r=1/2$</span>. We can connect the two large consumers in sequence, each of them <span class="math-container">$1/2$</span> of the time, and connect the small consumer in parallel to them.</li>
<li><span class="math-container">$(2,1,1)$</span>: <span class="math-container">$r=2/3$</span>. We can connect the large consumer in time <span class="math-container">$[0,2/3)$</span>, the second consumer in time <span class="math-container">$[0,1/3)\cup [2/3,1]$</span>, and the third one in time <span class="math-container">$[1/3,1]$</span>. Note that in each time the total consumption is at most <span class="math-container">$3$</span>.</li>
</ul>
<p>Two somewhat related problems are:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Bin_packing_problem" rel="nofollow noreferrer">Bin packing</a>. If the demands can be packed into <span class="math-container">$k$</span> bins of size <span class="math-container">$s$</span>, then <span class="math-container">$r\geq 1/k$</span>. But it is not tight, as shown by the example <span class="math-container">$(2,1,1)$</span> above.</li>
<li><a href="https://en.wikipedia.org/wiki/Parallel_task_scheduling" rel="nofollow noreferrer">Parallel task scheduling</a>. This problem involves tasks with &quot;length&quot; and &quot;width&quot;. The width is analogous to the demand in our problem, and the length is somewhat related to <span class="math-container">$r$</span>. But I did not find a variant in which this <span class="math-container">$r$</span> should be maximized.</li>
</ul>
<p>Is anything known about this problem?</p>

CC BY-SA 4.0
2021-06-27T04:36:04.830Z
It seems 2-Partition reduces to this problem proving NP-Completeness. Moreover, one can write a large exponential sized LP for optimum r and separation oracle for the dual seems to be the Knapsack problem. So one should be able to get an FPTAS via the known FPTAS for Knapsack. I am guessing this problem is known via some other name and perhaps related to Strip Packing?
Chandra Chekuri
<reference-request><scheduling><packing>
The "electricity packing" problem
Erel Segal-Halevi
# The "electricity packing" problem

(Asked by: username_0 on 2021-06-26)

The question is inspired by [this paper](https://link.springer.com/article/10.1007/s10458-019-09428-8).
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](https://en.wikipedia.org/wiki/Bin_packing_problem). 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](https://en.wikipedia.org/wiki/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?

**Tags:** reference-request, scheduling, packing

> **Comments:**
> **username_1**: It seems 2-Partition reduces to this problem proving NP-Completeness. Moreover, one can write a large exponential sized LP for optimum r and separation oracle for the dual seems to be the Knapsack problem. So one should be able to get an FPTAS via the known FPTAS for Knapsack. I am guessing this problem is known via some other name and perhaps related to Strip Packing?  

---

## 1 answers

### Answer by username_1 on 2021-06-27. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: Since there is an FPTAS, there should not be an analogous reduction from 3-partition (unless P=NP). But so far I could not find where exactly it fails.  
> **username_1**: @ErelSegal-Halevi Yes, good question re 3-partition. It does seem to be the case the the 3-partition can be reduced in a similar fashion. However, I wasn't sure if an FPTAS for approximating r implies an exact algorithm for 3-Partition. It seems to be connected to the fact that we do have an asymptotic FPTAS for Bin Packing.  

---

