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 we can write $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.

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.

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 we can write $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/s$ of the time, and get $r=1/s$. 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.

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 we can write $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.