Electricity division and bin packing

Question

In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$. The problem is that $s < \sum_i d_i$, so it is impossible to connect all households simultaneously. It is required to connect each household for a fraction $r$ of the time, such that $r$ is maximized.

For example, suppose the supply is $25$ and the demands are $11,12,13$. We can connect $11,12$ for one third of the time, and similarly $12,13$ and $13,11$ for one third of the time each. Note that each household is connected twice for $1/3$ of the time, so we get $r=2/3$. This clearly cannot be improved, so $r_{\max}=2/3$.

One way to find a reasonable electricity division is by reduction to bin packing. Suppose we can pack all demands into $q$ bins of capacity $s$; then we can connect each bin for $1/q$ of the time, and get $r=1/q$. But this is not optimal: in the above example, the optimal bin packing requires 2 bins, so we get $r=1/2$, but we already saw that $r_{\max}=2/3$.

We can do better by generalizing the bin-packing problem to a $k$-times-bin-packing: in this variant, there are $k$ copies of each item, and each bin must contain at most one copy of each item. Once we have a $k$-times-bin-packing into $q$ bins of capacity $s$, we can connect each bin for $1/q$ of the time, and get $r=k/q$. In the above example, with $k=2$, there is a packing into 3 bins, so we get the optimal value $r=2/3$.

It is easy to generate instances where $k=2$ does not lead to the optimal $r$. For example, for any $n$, suppose all $n$ demands are $1$, and the supply is $n-1$. Then $r_{\max} = \frac{n-1}{n}$, and it is attaind for $k=n-1$ and not for any smaller $k$.

QUESTIONS:

1. Is there always some finite $k$ for which $k$-times bin-packing leads to the optimal electricity division? That is: given $s,d_1,\ldots,d_n$, does there always exist a finite $k$ such that $r_{\max} = k/q_{k,\min}$, where $q_{k,\min}$ is the optimal number of bins in $k$-times bin-packing?

2. If the answer is yes, is there an upper bound on the optimal $k$, as a function of $n$?

NOTE: An answer by Chandra Chekuri to my question in cstheory.SE shows that the electricity division problem can be solved by a linear program with integer coefficients. Therefore, by well-known results, $r_{\max}$ is a rational number. But I could not deduce from this a positive answer to question 1.

Answer 1

Let us show that a required $k$-times bin-packing exists for some $k\le n^{n/2}$.

Let $V=\{(v_1,\dots,v_n)\in\{0,1\}^n:\sum_{i=1}^n d_iv_i\le s\}$ be the set of all admissible "bin packings". Then the convex hull $\operatorname{conv} V$ of $V$ is the set of all possible "schedules".

Let $e=(1,1,\dots,1)\in\mathbb R^n$. Then $r_\max=\sup\{r\in [0,1]:re\in\operatorname{conv} V\}$. Since the set $\operatorname{conv} V$ is compact, $r_\max$ is attained, that is $r_\max e\in \operatorname{conv} V$. We assume that the electricity division problem has a solution, so $r_\max>0$.

Here is an illustration, based on the example in the question:

The three blue points are the points in $V$, which are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$. The ray from the origin is $e\cdot \{r:r \ge 0\}$. The green point is the intersection of this ray with $\operatorname{conv} V$; its coordinates are $(2/3, 2/3, 2/3)$, which correspond to $r_{\max}=2/3$.

By Carathéodory's theorem, there exists an $n$ dimensional simplex $S$ with vertices in $V$ such that $r_\max e\in S$.

Let $V'$ be the set of the vertices of the face of $S$ of minimal dimension containing $r_\max e$. Clearly, $r_\max e$ is a boundary point of $S$, so $|V'|\le n$. In other words, the optimal electricity division can be constructed using most $n$ different configurations (in the example $V' = V$ and $|V'|=n=3$).

Let $(\lambda_v)_{v\in V'}$ be the barycentric coordinates of $r_\max e$, such that $\lambda_v>0$ for each $v\in V'$ and $\sum_{v\in V'}\lambda_v=1$ and $r_\max e =\sum_{v\in V'}\lambda_v v$. For instance, in the example $\lambda_v =1/3$ for each $v\in V'$.

We claim that the set $V'$ is linearly independent. Indeed, suppose for a contradiction that there exist disjoint nonempty subsets $V_1'$ and $V_2'$ of $V$ and positive numbers $(\mu_v)_{v\in V'_1\cup V_2'}$ such that $\sum_{v\in V_1'} \mu_v v=\sum_{v\in V_2'} \mu_v v$ and $\sum_{v\in V_1'} \mu_v \le \sum_{v\in V_2'} \mu_v$. Let $\nu=\min_{v\in V_2'} \lambda_v/\mu_v$. Then $$r_\max e =\sum_{v\in V'}\lambda_v v=\sum_{v\in V'}\lambda_v v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)=\sum_{v\in V'}\lambda_v' v,$$ where $$\lambda_v' v=\cases{ \lambda_v+\nu\mu_v, & if $v\in V_1'$,\\ \lambda_v-\nu\mu_v, & if $v\in V_2'$,\\ \lambda_v, & if $v\in V'\setminus (V_1'\cup V_2')$. }$$ Then $s=\sum_{v\in V'}\lambda_v'=\sum_{v\in V'}\lambda_v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)\le 1$, $\lambda_v'\ge 0$ for each $v\in V'$, and $\lambda_v'=0$ for some $v\in V_2'$. Then $s^{-1}r_\max e \in\operatorname{conv} V'\setminus\{v\}$, that contradicts to the minimality of $V'$.

Since the set $V''=V'\cup\{e\}$ is linearly dependent, by Lemma 2 from this answer to Integer coefficients in zero linear combinations of dependent vectors there exist integers $(\Delta_v)_{v\in V''}$ which are not all zeroes such that $|\Delta_v|\le n^{n/2}$ for each $v\in V''$ and $\sum_{v\in V''} \Delta_vv=0$. The set $V'$ is linearly independent, so $\Delta_e\ne 0$ and $e=\sum_{v\in V'} (-\Delta_v/\Delta_e) v=\sum_{v\in V'} (\lambda_v/r_\max) v$. Thus $-\Delta_v/\Delta_e=\lambda_v/r_\max>0$ for each $v\in V'$. Thus the coefficients $(|\Delta_v|)_{v\in V''}$ provide a required $|\Delta_e|$-times bin-packing.