💻 computer science

Time and Supply Fairness in Electricity Distribution using $k$ -times bin packing

This paper introduces the $k$ -times bin packing problem to model fair electricity distribution, proving its applicability to connection time allocation while demonstrating that generalizations of First-Fit algorithms outperform existing heuristics, and further addressing the more complex watt allocation variant through new heuristic benchmarks despite proving an impossibility result for finite $k$ .

Original authors: Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

Published 2026-05-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Power Cut" Problem

Imagine a small village where the local power station can only generate enough electricity to run half the houses at once. The village has 100 families, but the grid can only handle 50. If they try to turn everyone on at once, the system crashes.

The village elders need a fair way to share the power.

The Old Way: They might split the village into two groups. Group A gets power for 12 hours, then Group B gets power for 12 hours. Everyone gets 50% power.
The Problem: This isn't always the fairest. Maybe Family X needs a lot of power for a big fridge, while Family Y only needs a little for a lightbulb. If they just swap groups, Family X might still be unhappy because their "slice" of the pie is too small to run their fridge effectively.

The authors of this paper propose a smarter way to slice the pie, using a mathematical puzzle called Bin Packing.

The Puzzle: "k-times Bin Packing"

To understand their solution, let's play a game with suitcases.

The Classic Game (Bin Packing):
You have a bunch of suitcases of different sizes and a truck with a fixed cargo space. Your goal is to pack as many suitcases as possible into the fewest number of trucks.

In the paper's context: The "suitcases" are households' electricity needs. The "truck" is the power station's capacity.

The New Game (k-times Bin Packing):
The authors invented a twist. They say: "Okay, pack the suitcases into trucks, but here is the rule: Every single suitcase must appear in exactly k different trucks."

The Analogy: Imagine you have a favorite book. You want to make sure that book is available in k different libraries so that if one library is closed, you can still find it elsewhere. But you can't put two copies of the same book in the same library.
Why do this? By forcing every household to appear in multiple "groups" (trucks), you can rotate the power on and off more frequently. Instead of Group A getting power for 12 hours straight, you might have 10 different groups, and every family gets power for 1 hour, then 1 hour off, then 1 hour on again. This smooths out the experience and makes it feel fairer.

The Main Discovery: How Many Copies Do We Need?

The authors asked a deep mathematical question: "Is there a magic number k that guarantees the fairest possible outcome?"

The Answer: Yes! They proved that for any village size, there is a specific number k (which depends only on how many families there are) that allows you to achieve the absolute maximum fairness.
The Catch: Finding the perfect packing is a math nightmare (it's "NP-hard," meaning it takes too long for computers to solve perfectly for huge villages).
The Solution: Since we can't find the perfect answer instantly, the authors took famous, fast algorithms (like First-Fit and First-Fit Decreasing) and tweaked them to handle this "k-times" rule.
- First-Fit: Imagine you have a line of people. You put the first person in the first empty seat. If they don't fit, you open a new seat.
- The Tweak: They modified this so that as they fill seats, they ensure everyone gets to sit in k different seats over time.

The Result: Their modified algorithms are incredibly efficient. They run almost as fast as the old methods but provide a much fairer distribution of power. In tests using real data from 367 households in Nigeria, their method gave people more hours of power and a more even distribution than previous methods.

The Second Challenge: "Fair Watts" vs. "Fair Time"

The paper also tackled a second, trickier problem.

Scenario A: Fair Time
"Everyone gets the same amount of time connected to the grid."

Analogy: Everyone gets to sit in the hot tub for exactly 10 minutes.
Result: This is what the "k-times bin packing" solves perfectly.

Scenario B: Fair Watts (Power Amount)
"Everyone gets the same amount of electricity (energy), regardless of how long they are connected."

Analogy: Everyone gets exactly 10 liters of water.
- If you have a small cup (low demand), you might need to be connected for a long time to get 10 liters.
- If you have a giant bucket (high demand), you might get your 10 liters very quickly.
The Problem: The authors proved that for this specific goal, there is no magic number k that works for everyone. Sometimes, to make it perfectly fair, you would need an infinite number of groups, which is impossible.

The Workaround:
Since a perfect mathematical solution doesn't exist for "Fair Watts," the authors created four "Heuristic" (smart guess) algorithms.

Think of these as four different strategies a village chief might use to try to be as fair as possible.
They tested these strategies and found that one specific strategy (called HA1 combined with their modified packing algorithm) was the best at ensuring the person with the least power still got a decent amount of electricity.

Summary of Findings

The "k-times" trick works: By forcing every household to be part of multiple power-sharing groups, you can create a much fairer schedule than just splitting people into two big groups.
Fast and Fair: They adapted standard computer algorithms to do this quickly. In real-world tests, these new algorithms gave households more connection time and less inequality than existing methods.
Time vs. Power: It is mathematically easy to make the time fair for everyone. It is mathematically impossible to make the exact amount of power (watts) perfectly fair for everyone using a simple repeating pattern. However, their new "smart guess" algorithms get very close to the best possible outcome.

In short: The paper provides a new, mathematically proven way to slice the electricity pie so that no one feels like they are getting the "short end of the stick," especially in places where there isn't enough power for everyone at once.

Technical Summary: Time and Supply Fairness in Electricity Distribution using k-times bin packing

1. Problem Definition

The paper addresses the problem of fair electricity distribution in developing countries where total household demand exceeds available supply capacity ( $S$ ). The core challenge is to allocate limited electricity among $n$ households with varying demands ( $D$ ) in a way that maximizes fairness.

The authors define two distinct optimization objectives:

Egalitarian Allocation of Connection Time: The goal is to maximize the minimum amount of time any household is connected to the grid. The utility of an agent is binary: they gain utility only if their full demand is met during a time interval; partial fulfillment yields zero utility. This models scenarios where activities require a specific power threshold to function.
Egalitarian Allocation of Watts (Supply): The goal is to maximize the minimum amount of electrical energy (in kWh) allocated to any household. Unlike the time-based model, this considers the volume of electricity delivered, aiming to equalize the total energy received by agents, even if their connection times differ.

The paper formalizes the time-based problem as a variant of the classic Bin Packing Problem, termed k-times bin-packing (kBP). In kBP, given a set of items (demands) and bin capacity $S$ , the objective is to pack items into the minimum number of bins such that:

The sum of item sizes in each bin does not exceed $S$ .
Each item appears in exactly $k$ distinct bins.
No bin contains more than one copy of the same item.

2. Methodology and Theoretical Framework

Theoretical Foundations

The authors establish a theoretical link between the electricity division problem and kBP.

Existence of Optimal $k$ : They prove that for any electricity division instance with $n$ households, there exists a finite integer $k$ such that solving the kBP problem optimally yields the optimal solution for the egalitarian connection-time problem.
Bounds on $k$ : The paper provides an upper bound for this $k$ based on the number of households $n$ , specifically $k \le a(n)$ , where $a(n)$ is the maximal determinant of an $n \times n$ binary matrix (related to Hadamard matrices). A lower bound of $k \ge n-1$ is also established for specific instances.
Impossibility for Watts: Conversely, for the egalitarian allocation of watts, the authors prove an impossibility result: there is no finite $k$ that depends only on the number of agents $n$ to guarantee an optimal solution. This is because optimal solutions may require agents with smaller demands to be connected for significantly longer durations, requiring unbounded repetition ratios.

Algorithmic Extensions

Since kBP is NP-hard, the paper focuses on extending existing bin-packing approximation algorithms to the kBP setting:

Fast Constant-Factor Approximations:
- $FF_k$ (First-Fit): The authors extend the First-Fit algorithm to process $k$ copies of the input instance ( $D^k$ ). They prove an asymptotic approximation ratio of $(1.5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$ . As $k$ increases, the ratio approaches 1.5, improving upon the standard First-Fit ratio of 1.7.
- $FFD_k$ (First-Fit Decreasing): The authors extend First-Fit Decreasing. While a tight upper bound is not proven, they conjecture an asymptotic ratio of $11/9$ (approx. 1.22) based on simulation data, improving upon the standard FFD ratio.
- $NF_k$ (Next-Fit): The extension of Next-Fit is shown to have an asymptotic ratio of 2.
Polynomial-Time Approximation Schemes (PTAS):
- The paper generalizes the Fernandez de la Vega-Lueker and Karmarkar-Karp algorithms.
- The extension of Fernandez de la Vega-Lueker achieves $(1 + 2\epsilon)OPT(D^k) + k$ bins.
- The extensions of Karmarkar-Karp Algorithms 1 and 2 provide solutions with additive terms dependent on $k$ and $\epsilon$ , running in polynomial time.
Heuristics for Watts Allocation:
- Due to the impossibility of a universal $k$ for watts allocation, the authors propose four heuristic algorithms (HA1–HA4).
- These heuristics employ a two-step process:
  1. Identify a subset of agents with the smallest demands to be connected continuously (all the time).
  2. Apply kBP-based strategies (using $FF_k$ or $FFD_k$ ) to the remaining agents and reduced supply to maximize the minimum watt allocation.
- The algorithms utilize ternary search to determine the optimal size of the continuously connected subset ( $g$ ) that maximizes the leximin vector (prioritizing the worst-off agent).

3. Key Results and Experimental Evaluation

Theoretical Results

Approximation Ratios: The paper provides rigorous proofs for the approximation ratios of $FF_k$ and $NF_k$ . For $FF_k$ , the ratio improves as $k$ grows, theoretically converging to 1.5.
Impossibility: The proof that no finite $k$ (dependent only on $n$ ) suffices for egalitarian watts allocation motivates the shift to heuristic approaches for this specific variant.

Experimental Results

The authors evaluated their algorithms using two datasets:

Synthetic Data: Generated instances with known optimal solutions to verify the approximation ratios of $FF_k$ and $FFD_k$ . Results supported the conjecture that $FF_k$ achieves a ratio of 1.375 and $FFD_k$ achieves $11/9$ for $k > 1$ .
Real-World Data: A dataset of 367 households from Nigeria (from Oluwasuji et al. [34, 35]) covering 13 weeks of hourly demand.

Performance on Connection Time (Egalitarian Time):

The $FF_k$ and $FFD_k$ algorithms (tested with $k=100$ ) significantly outperformed existing heuristic and ILP-based methods (such as the Comfort Model and Supply Model from [35]) in terms of egalitarian connection time.
They achieved near-zero maximum utility differences between agents, indicating highly equitable distribution.
The algorithms ran in nearly linear time relative to the number of agents.

Performance on Watts Allocation (Egalitarian Watts):

Among the four heuristics, HA1 (using $FFD_k$ ) performed best in supplying the maximum amount of electricity to the worst-off agent.
HA4 (using $FF_k$ ) outperformed others in total watts delivered and total connection time.
The heuristics successfully balanced the trade-off between connecting small-demand agents continuously and fairly distributing the remaining supply to larger-demand agents.

4. Significance and Claims

The paper claims to provide a practical, fair, and efficient framework for electricity division in resource-constrained environments. Its primary contributions are:

Formalization: Defining the k-times bin-packing problem as a mathematical abstraction for fair resource allocation where items must be replicated across disjoint sets.
Algorithmic Improvement: Demonstrating that extending standard bin-packing heuristics to the kBP setting yields better approximation ratios than the original algorithms, specifically improving the egalitarian outcome for connection time.
Practical Application: Validating that these theoretical extensions can solve real-world load-shedding problems more effectively than previous state-of-the-art methods, particularly in maximizing the minimum connection time for all households.
New Benchmarks: Establishing new benchmarks for the egalitarian allocation of watts, showing that while a theoretical optimal $k$ does not exist, heuristic approaches can yield superior fairness metrics compared to existing solutions.

The authors conclude that using kBP offers a viable path to fair electricity distribution, particularly when the objective is to maximize the time each agent is connected, and that heuristic adaptations are necessary and effective for maximizing the fairness of energy volume (watts) delivered.