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.

Rescheduling problems arise when unpredicted events occur, such as the arrival of new orders. These new jobs should be integrated in a proper way in the existing schedule of the so-called old jobs, with the aim of minimizing an objective function for the joint set of jobs. To avoid a major disruption of the original schedule, each old job is not allowed to deviate from its original completion time by more than a certain threshold. Filling a gap in the existing literature, we consider the minimization of the total weighted completion time. The resulting rescheduling problem is shown to be weakly NP-hard and several properties of the structure of an optimal schedule are derived. These can be used for the construction of an exact dynamic programming algorithm with pseudo-polynomial running time. A fully polynomial time approximation scheme is obtained from the dynamic program by three different scaling and reduction steps. Finally, for the minimization of the number of late jobs a strong NP-hardness result is derived. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was partially supported by the Ministero dell’Istruzione, dell’Università e della Ricerca [Award TESUN-83486178370409 finanziamento dipartimenti di eccellenza CAP. 1694 TIT. 232 ART. 6]. U. Pferschy acknowledges support by the Field of Excellence COLIBRI at the University of Graz.

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).

This paper studies the allocation of indivisible items to agents, when each agent’s preferences are expressed by means of a directed acyclic graph. The vertices of each preference graph represent the subset of items approved of by the respective agent. An arc (a,b) in such a graph means that the respective agent prefers item a over item b. We introduce a new measure of dissatisfaction of an agent by counting the number of non-assigned items which are approved of by the agent and for which no more preferred item is allocated to the agent. Considering two problem variants, we seek an allocation of the items to the agents in a way that minimizes (i) the total dissatisfaction over all agents or (ii) the maximum dissatisfaction among the agents. For both optimization problems we study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures, such as stars, trees, paths, and matchings. We also analyze the parameterized complexity of the two problems with respect to various parameters related to the number of agents, the dissatisfaction threshold, the vertex degrees of the preference graphs, and the treewidth.

In recent years, an increasing number of cities has started to deploy electric buses in test or demonstration phases. Among many different variants of electric technologies, usually a small number of buses of a selected technology type is ordered and operated on a single bus line. Few experiences were made with regard to a full fleet conversion, which requires an in-depth assessment of local operating conditions for different technologies and is accompanied by a number of complex, interrelated strategic and operational decisions. The goal of this work is to identify an optimal composition of electric technologies for the fleet of an urban bus network. Specifically, hydrogen-powered fuel cell buses, overnight or opportunity charging buses can be chosen. By minimizing total cost of ownership, the optimal technology for each bus line is selected and vehicle and charging schedules as well as spatial distribution of charging stations and infrastructure dimensions at the depot are optimized.

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.

We study the multidimensional knapsack problem, present some theoretical and empirical results about its structure, and evaluate different integer linear programming (ILP)-based, metaheuristic, and collaborative approaches for it. We start by considering the distances between optimal solutions to the LP relaxation and the original problem and then introduce a new core concept for the multidimensional knapsack problem (MKP), which we study extensively. The empirical analysis is then used to develop new concepts for solving the MKP using ILP-based and memetic algorithms. Different collaborative combinations of the presented methods are discussed and evaluated. Further computational experiments with longer run times are also performed to compare the solutions of our approaches to the best-known solutions of another so-far leading approach for common MKP benchmark instances. The extensive computational experiments show the effectiveness of the proposed methods, which yield highly competitive results in significantly shorter run times than do previously described approaches.