Ulrich Pferschy

Francesco Corti, Balz Maag, Joachim Schauer et al.

Deep learning models deployed on edge devices frequently encounter resource variability, which arises from fluctuating energy levels, timing constraints, or prioritization of other critical tasks within the system. State-of-the-art machine learning pipelines generate resource-agnostic models that are not capable to adapt at runtime. In this work, we introduce Resource-Efficient Deep Subnetworks (REDS) to tackle model adaptation to variable resources. In contrast to the state-of-the-art, REDS leverages structured sparsity constructively by exploiting permutation invariance of neurons, which allows for hardware-specific optimizations. Specifically, REDS achieves computational efficiency by (1) skipping sequential computational blocks identified by a novel iterative knapsack optimizer, and (2) taking advantage of data cache by re-arranging the order of operations in REDS computational graph. REDS supports conventional deep networks frequently deployed on the edge and provides computational benefits even for small and simple networks. We evaluate REDS on eight benchmark architectures trained on the Visual Wake Words, Google Speech Commands, Fashion-MNIST, CIFAR-10 and ImageNet-1K datasets, and test on four off-the-shelf mobile and embedded hardware platforms. We provide a theoretical result and empirical evidence demonstrating REDS' outstanding performance in terms of submodels' test set accuracy, and demonstrate an adaptation time in response to dynamic resource constraints of under 40$μ$s, utilizing a fully-connected network on Arduino Nano 33 BLE.

Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy

A new class of multi agent single machine scheduling problems is introduced, where each job is associated with a self interested agent with a utility function decreasing in completion time. We aim to achieve a fair solution by maximizing the minimum utility across all agents. We study the problem's complexity and propose solution methods for several variants. For the general case, we present a binary search procedure to find the largest possible minimum utility, as well as an exact greedy based alternative. Variants with release and due dates are analyzed, showing strong NP hardness for arbitrary release dates, but weak NP hardness for a single release date job, and polynomial solvability when all jobs share processing times. For all these cases we also study the corresponding problem of finding efficient solutions where the sum of utilities is maximized. We also examine settings where linear utility functions can be adjusted within budget constraints, exploring the impact on optimal schedules when intercepts or slopes are modified. From a single agent perspective, we investigate the effect of improving one agent's utility in the overall solution. Adding a new job to be inserted with the best possible utility gives rise to rescheduling problems, where different lower bounds depending on the utilities of the original fair schedule are imposed. Finally, we consider a bi level setting where a leader wants to enforce a certain target schedule by modifying utility functions while the follower computes a fair solution for the modified instance. Our work contributes to scheduling theory, multi agent systems, and algorithmic fairness, highlighting fairness oriented objectives in competitive scheduling.