Resource Allocation in Networks

TY - GEN

T1 - Resource Allocation in Networks

AU - Logins, Alvis

PY - 2020/6/29

Y1 - 2020/6/29

N2 - Given the spatial locations of customers and a road network, where to build new facilities that would satisfy the customers needs? How to allocate vaccination centres in a country to suppress a virus epidemics? Which Twitter accounts can advertise a piece of news to the largest auditory and in the most robust way? Prima facie, the questions are disparate, but all derive from the generic problem of \emph{Resource Allocation in Networks}. Given network nodes representing a set of consumers and a set of possible resource locations, the goal is to minimize the loss or maximize the profit of allocating a limited budget of indivisible resources. Interacting with a resource occurs via a connection from supply to demand nodes through network edges with certain characteristics like capacity, cost, weight, or probability. Such a process may occur with or without a restriction of flow preservation at nodes, by which inflow to a node is equal to outflow, resulting to a \emph{transportation} in the former case and to a \emph{diffusion} in the latter case. This thesis investigates methods and solutions for this family of resource allocation problems with respect to the transportation and diffusion models, building on previous work in the fields of Operations Research, Machine Learning, and Data Management, considering temporal and stochastic components. We propose novel techniques to calculate model parameters and to achieve objectives of convenience in facility location, fairness in vehicle cruising, and robustness in diffusion control problems, with a good balance between scalability and quality. Our experimental studies based on real-world datasets show the efficiency and effectiveness of the solutions.

AB - Given the spatial locations of customers and a road network, where to build new facilities that would satisfy the customers needs? How to allocate vaccination centres in a country to suppress a virus epidemics? Which Twitter accounts can advertise a piece of news to the largest auditory and in the most robust way? Prima facie, the questions are disparate, but all derive from the generic problem of \emph{Resource Allocation in Networks}. Given network nodes representing a set of consumers and a set of possible resource locations, the goal is to minimize the loss or maximize the profit of allocating a limited budget of indivisible resources. Interacting with a resource occurs via a connection from supply to demand nodes through network edges with certain characteristics like capacity, cost, weight, or probability. Such a process may occur with or without a restriction of flow preservation at nodes, by which inflow to a node is equal to outflow, resulting to a \emph{transportation} in the former case and to a \emph{diffusion} in the latter case. This thesis investigates methods and solutions for this family of resource allocation problems with respect to the transportation and diffusion models, building on previous work in the fields of Operations Research, Machine Learning, and Data Management, considering temporal and stochastic components. We propose novel techniques to calculate model parameters and to achieve objectives of convenience in facility location, fairness in vehicle cruising, and robustness in diffusion control problems, with a good balance between scalability and quality. Our experimental studies based on real-world datasets show the efficiency and effectiveness of the solutions.

M3 - PhD thesis

T3 - PhD Theses - Department of Computer Science

PB - Aarhus Universitet

ER -