Sequential Resource Allocation for network diffusion control.

Summary Dynamic containment of an undesirable network diffusion process, such as an epidemic, requires a decision maker (DM) to be able to respond to its evolution by taking the right control measures at the right time. This task can be viewed as managing the allocation of a limited amount of resources to network nodes, with the objective of reducing the effects of the process.In this thesis, we extend the dynamic resource allocation (DRA) problem and pro- posit a dynamic control framework with multiple iterations/turns, which we realize through two derived models: restricted DRA and sequential DRA (RDRA, SDRA). Unlike standard considerations in which information and access are complete, these new models take into account possible access restrictions regarding the information available on the network and/or the ability to act on its nodes. At each intervention cycle, the DM has limited access to information about a fraction of the nodes, and also gains access to act on them sequentially.This latter sequential aspect in the decision process offers a completely new perspective to the control of the dynamic diffusion process, making this work the first to present the dynamic control problem as a series of sequential selection processesIn the sequential selection problem (SSP), immediate and irrevocable decisions must be made by the decision maker, while candidates arrive in a random order and are considered for one of the available selection slots. For the purposes of network broadcast control, what we pro- pose is to select the right nodes to allocate control resources to in a sequential, multi-iteration process. However, standard SSP vari- ants, such as the well-known secretary problem, start with an empty selection set (cold start) and perform the selection process once on a single set of candidates (single iteration). Both of these limitations are addressed in this thesis. First, we introduce a new hot-start setting that considers having a reference set at hand, i.e., a set of previously selected elements of a given quality. The DM then attempts to optimally update this set while examining the sequence of arriving candidates, constrained by the possibility of updating the assignment to each selection slot (resource) at most once. The sequential selection pro- cess with multiple iterations, is then introduced as a natural extension of hot-start selection.Objective functions based on the rank and score of the final selection are considered. An approach based on the separation of the sequence into two phases is proposed for the first one, while the optimal strategy based on the computation of a dy- namic acceptance threshold is derived for the second one assuming that the distribution of scores is known. These strategies are then compared for their efficiency in the context of traditional selection as well as for the resolution of the network control problems that motivated this thesis. The generality of the models introduced allows their application to a wide variety of domains and problems. For example, recurrent recruitment processes, resource management (e.g., beds, staff) in health care units, as well as the solution of difficult constrained combinatorial problems, such as the b-diversification problem found in data flow processing applications (e.g., in robotics).