4
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$ Jun 27, 2021 at 4:36

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jun 29, 2021 at 4:47
  • $\begingroup$ 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. $\endgroup$ Jun 29, 2021 at 7:55
  • $\begingroup$ @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. $\endgroup$ Jun 29, 2021 at 21:06

Your Answer

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

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