cs.DSMay 12, 2026

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

Authors: Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

Organizations: Ariel University, Ariel 40700, Israel · UPES, Dehradun, Uttarakhand, India · Pidstryhach Institute for Applied Problems of Mechanics and Mathematics of National Academy of Sciences of Ukraine, Lviv, Ukraine

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into the minimum number of bins such that the sum of the item sizes in each bin does not exceed the capacity. We define a new variant, k-times bin-packing (kBP), in which the goal is to pack the items so that each item appears exactly k times in k different bins. We generalize existing approximation algorithms for bin-packing to solve kBP and analyze their performance ratios. The fair electricity division problem motivates the study of kBP. The goal is to allocate the available supply among households using some fairness criteria, such as the egalitarian principle. We prove that every electricity division problem can be solved by k-times bin-packing for some finite k, which depends only on the number of households. We implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve kBP and apply them to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem in terms of the egalitarian allocation of connection time. We study another variant of the egalitarian allocation problem, in which the goal is to maximize the minimum number of watts allocated to a household. For this variant, we prove an impossibility result: there does not exist such a k that depends only on the number of agents. This impossibility result motivates us to develop four different heuristic algorithms to solve the egalitarian allocation of watts problem. We evaluate the heuristics by summing the minimum watts allocated to any household in each hour, yielding a fairness metric that reflects the lowest watt allocation across all hours. A higher total minimum of watts indicates a more equitable distribution. Thus, we establish new benchmarks for fair allocation of watts.

Explore similar work

CardsList
Apr 30, 2026cs.AI

Fairness for distribution network operations and planning

The incorporation of fairness into the distribution network (DN) planning and operation has become a key goal of recent studies. The cost of implementing fairness, denominated the price of fairness (PoF), covers the efficiency that is renounced for attaining social cohesion through fair outcomes. Locational disparity makes fairness schemes emerge to level the consumers playing field. However, fairness encompasses a range of notions. From egalitarian to merit-based criteria, various metrics are implemented as a tool for measuring equitable utility distribution. These have different mathematical complexities, from linear to non-linear programming cases, which affect their overall applicability. Hence, this study compiles the overarching fairness notions and metrics, reviewing how these affect stakeholders and the inherent mathematical optimisation in resource allocation problems. The aim is to support consistent and transparent planning and decision-making within DN operations.
Pedro F. C. de Carvalho, Zijie Liu, Md Umar Hashmi +1
Fairness ConstraintsNetworked SystemsWelfareMixed-Integer ProgrammingPlanning Methods
AskPDF
Jul 25, 2026cs.GT

Online Fair Division with Budget Constraints

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.
Saar Cohen, Nicholas Teh, Paul W. Goldberg +1
Knapsack ConstraintFairness ConstraintsToken Budgets
AskPDF
Sep 7, 2026cs.CG

A Sub-4 Approximation for Fair kk-Means

Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair kk-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets. Given a ρρ-approximate algorithm for weighted kk-means and any ε>0ε>0, our algorithm returns a fractional solution whose cost is at most 1+(3−1/Γ)ρ+O(ε)1+(3-1/Γ)ρ+O(ε) times the optimal integral fair cost, where Γ≈6.357Γ\approx6.357 is an upper bound on the integrality gap of the standard Euclidean kk-means LP. With a PTAS as the subroutine, the approximation ratio becomes 3.8427+O(ε)3.8427+O(ε), improving the previous factor of 5+O(ε)5+O(ε) to below 44. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the kk-sparse Wasserstein barycenter problem.
Kangke Cheng, Guanlin Mo, Shihong Song +1
K-MeansApproximation AlgorithmsFairness-Aware LearningApproximation
AskPDF