Skip to main content
5 of 18
added 136 characters in body

Unfortunately, now I cannot devote much time to your question, thus the answer below can be superficial and not very checked, so I shall try to improve it later. On the other hand, I expect it should provide a positive answer to both your questions.

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$.

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

enter image description here

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 $r\cdot e$. The green point is the intersection of this ray with $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$ (in the example $\lambda_v =1/3$ for all $v\in V'$).

Define a set of $n$ vectors: $F := \{ n\cdot v - \langle v,e\rangle \cdot e | v\in V'\}$. We claim that these vectors are linearly independent. Indeed, let $f := \sum_{v\in V'}\lambda_v \cdot (n\cdot v-\langle v,e\rangle \cdot e)$. It is easy to check that $f$ is both collinear and orthogonal to $e$, so $f=0$. Thus $F$ is linearly dependent.

I expect that Lemma from this answer implies that there exist integers $(\lambda_f)_{v\in V'}$ bounded by a function of $n$, which are not all zeroes and $\sum_{v\in V'}f_v (nv-(v,e)e)$. I expect that the minimality of $V'$ implies that $(f_v)_{v\in V'}$ is proportional to $(\lambda_v)_{v\in V'}$, so $(f_v)_{v\in V'}$ provides the required some-times-bin-packing.

Alex Ravsky
  • 5.4k
  • 1
  • 17
  • 31