Data plays an ever-greater role today: whether we are navigating to new destinations or scheduling jobs for people, planes and processors, data plays an important role in arriving at a good solution. As infrastructure increases, road networks and airports expand and, consequently, the data sets become enormous. Massive data sets demand computation schemes or algorithms that are computationally efficient; ideally, they only consider each data point a few times on average. This ensures that the computational resources required scale nicely with the size of the problem being solved. In the classical algorithmic setting, one optimizes with this goal in mind: Given a data set, how efficiently can we calculate the required analysis?
Many modern problems, however, are inherently dynamic: when traffic forms on the highway, it may be faster to reroute your trip, or when a flight is delayed, it might be sensible to restructure the departure schedule for that day. Many of these changes are local; they affect only one data point: the status of a specific highway or airplane. Despite the changes being small, in the classical setting one must reconsider the entire data set to accommodate them. For massive data set this might not be desirable. As such, much recent research has gone into studying dynamic algorithms that can facilitate local updates and recompute good solutions efficiently.
Many modern problems can be modelled as graphs. A graph is a collection of points together with a set of edges or connections between the points. Typically, the edges model compatibility or conflict. For instance, a road network can be modeled by viewing locations as points and connections between them as edges. A route can then be viewed as a consecutive sequence of edges in the corresponding graph. Many problems share the same underlying abstract structure; matching resources to processors is no different from matching planes to trips. Thus, if one can solve the abstracted version of the problem, one develops tools that can be applied in many different settings and arenas. 2 The goal of this project is to use tools from mathematics and computer science to devise and analyze algorithms that efficiently recompute solutions to such abstract problems on dynamic graphs.