Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
This addresses the problem of balancing resource efficiency and fairness in networked systems for applications like distributed learning, but it is incremental as it builds on existing temporal network and fairness concepts.
The paper tackles the Fair Minimum Labeling (FML) problem, which involves designing a minimum-cost temporal edge activation plan to ensure equitable access for node groups in networks, showing it is NP-hard and presenting approximation algorithms that match the best possible cost guarantee. Empirical results demonstrate that FML enforces group-level fairness with substantially lower activation cost than baselines in a fair multi-source data aggregation task.
Balancing resource efficiency and fairness is critical in networked systems that support modern learning applications. We introduce the Fair Minimum Labeling (FML) problem: the task of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set, according to specified coverage requirements. FML captures key trade-offs in systems where edge activations incur resource costs and equitable access is essential, such as distributed data collection, update dissemination in edge-cloud systems, and fair service restoration in critical infrastructure. We show that FML is NP-hard and $Ω(\log |V|)$-hard to approximate, where $V$ is the set of nodes, and we present probabilistic approximation algorithms that match this bound, achieving the best possible guarantee for the activation cost. We demonstrate the practical utility of FML in a fair multi-source data aggregation task for training a shared model. Empirical results show that FML enforces group-level fairness with substantially lower activation cost than baseline heuristics, underscoring its potential for building resource-efficient, equitable temporal reachability in learning-integrated networks.