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$\mu$s, utilizing a fully-connected network on Arduino Nano 33 BLE.

Abstract We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Namely, we introduce an incompatibility relation between pairs of items described in terms of a conflict graph. Every subset of items assigned to one agent has to form an independent set in this graph. Thus, the allocation of items to the agents corresponds to a partial coloring of the conflict graph. Every agent has its own profit valuation for every item. Aiming at a fair allocation, our goal is the maximization of the lowest total profit of items allocated to any one of the agents. The resulting optimization problem contains, as special cases, both Partition and Independent Set. In our contribution we derive complexity and algorithmic results depending on the properties of the given graph. We show that the problem is strongly NP-hard for bipartite graphs and their line graphs, and solvable in pseudo-polynomial time for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. Each of the pseudo-polynomial algorithms can also be turned into a fully polynomial approximation scheme (FPTAS).

We study the approximability of the classical quadratic knapsack problem (QKP) on special graph classes. In this case the quadratic terms of the objective function are not given for each pair of knapsack items. Instead, an edge weighted graph, whose vertices represent the knapsack items, induces a quadratic profit for every pair of items, which is adjacent in the graph. We show that the problem permits an FPTAS on graphs of bounded treewidth and a PTAS on planar graphs and more generally on H-minor free graphs. We also show strong 𝒩𝒫-hardness of QKP on graphs that are 3-book embeddable, a natural graph class that is related to planar graphs. In addition, we will argue that the problem is likely to have bad approximability behaviour on all graph classes that include the complete graph or contain large cliques. These hardness of approximation results under certain complexity assumptions carry over from the densest k-subgraph problem.

In this contribution we present an optimization model for deciding on the best selection of advertising media to be used in a promotional campaign. The effect of each single medium and each pair of media is estimated from the evaluation data of past campaigns taking into account a similarity measure between the attributes and goals of campaigns. The resulting discrete optimization model is a Quadratic Knapsack Problem which we solve by a genetic algorithm. Then campaign budget is assigned to each selected advertising medium based on a statistical estimation from previous campaigns. Our optimization tool is integrated in the marketing management software solution MARMIND.