$k$-times bin packing and its application to fair electricity distribution

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called \emph{$k$-times bin-packing ($k$BP)}, where the goal is to pack the items such that each item appears exactly $k$ times, in $k$ different bins. We generalize some existing approximation algorithms for bin-packing to solve $k$BP, and analyze their performance ratio. The study of $k$BP is motivated by the problem of \emph{fair electricity distribution}. In many developing countries, the total electricity demand is higher than the supply capacity. We prove that every electricity division problem can be solved by $k$-times bin-packing for some finite $k$. We also show that $k$-times bin-packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve $k$BP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem.