Dynamic and sublinear algorithms for local problems

Large-scale data applications in practice have led to the emergence of computational models such as dynamic and sub-linear that focus on maintaining data structures over evolving datasets and solving optimization problems without accessing most of the underlying data, respectively. Optimization problems requiring more `local` guarantees over the input appear to admit efficient algorithms in these models. This project aims to introduce algorithm design techniques for dynamic and sub-linear models and explore principles that yield efficient algorithms in both. Specifically, it explores this direction in the context of fundamental local optimization problems, including the approximate maximum matching, and the graph edge colouring problems, along with their generalizations. The maximum matching problem seeks to find the largest possible matching in a graph. The problem has historically been a cornerstone of combinatorial optimization research and has a wide range of practical applications such as job assignment, network design, resource allocation, vehicle routing and scheduling, amongst others. The related edge colouring problem asks us to partition the edges of a graph into a small number of matchings. It has found applications in scheduling, telecommunications, allocation problems and parallel processing. Both problems (particularly their approximate versions) can be described as local problems in the sense that we can define properties concerning the immediate neighbourhood of vertices which if satisfied, define valid outputs. For intuitive reasons, local problems appear to admit efficient dynamic and sub-linear algorithms. A dynamic algorithm that works with evolving inputs can make quicker adjustments to its output if the effect of the changes is local. Sub-linear algorithms can locally compute parts of the output from which it can infer statistics for the whole data. This project will aim to settle long-standing open problems concerning matching and edge colouring and their generalizations in the dynamic and sub-linear models. As part of achieving this goal, it will focus on defining algorithm design techniques that can be widely applied to local optimization problems yielding algorithms implementable in multiple computational models.