Theory and Applications of Dynamic Algorithms

A fundamental aspect of many large scale systems is that the input to these systems are inherently "dynamic" in nature. Indeed, this happens to be the case with social networks like Facebook and Twitter, transport networks that are meant to be tracked in google maps, and data centres which support the increasingly popular cloud computing services. All these systems need to cope with the fact that the input data changes very rapidly over time. Friendship links get created and destroyed in the social networks every moment, the congestion on any given road in a transport network changes from one time of the day to another, and a cloud computing system like Microsoft Azure has to serve users that arrive and depart in an online manner. This leads us to one of the key challenges in dealing with "big data" under limited computational resources: How can an algorithm quickly update the solution to a computational problem after observing an update (i.e., change in its input)? A naive solution here will be to recompute the solution from scratch after every update. Is there any way one can do significantly better than this naive approach?

The project will lead to major advances in our understanding of "dynamic algorithms", which is an important research area within theoretical computer science that is concerned with addressing precisely the question described above. The project will consist of three strands of work. The first two strands will develop a unified framework for dynamic algorithm design for fundamental computational problems, by exporting the popular paradigms for designing efficient static algorithms into the dynamic world. Specifically, it will focus on problems that admit fast primal-dual and greedy algorithms in the static setting, and convert them into fast algorithms in the dynamic setting. This will improve the state of the art dynamic bounds for multiple fundamental computational problems such as maximum matching, packing/covering linear programs, maximal independent set and finding dense subgraphs. The third strand will consider dynamic resource allocation problems that are of relevance to data centres and cloud systems, and it will build efficient dynamic algorithms for these problems.

The project deals with a fundamental research topic and it will contribute towards significant advances in this important research area within Theoretical Computer Science.

The project will make fundamental contributions in a vibrant area of research within theoretical computer science. Furthermore, in many industrial applications one needs to cope with the fact that the input data to a concerned computational system evolves rapidly over time. This is indeed the case with modern day data centres, cloud service systems and social networks like Facebook and Twitter. This specific issue is at the heart of the study of dynamic algorithms, albeit in a general and abstract setting. Thus, theoretical insights stemming from this project have the potential to impact various industries that have to deal with the challenge of dynamic input data.

To achieve this impact, the PI will work with Dr. Janardhan Kulkarni (Microsoft Research, Redmond) on dynamic resource allocation problems that are of relevance to Microsoft data centres and Azure cloud computing system. Dr. Kulkarni will be contributing as a project partner. The PI and the PDRA will make visits to Dr. Kulkarni's research lab in Microsoft, Redmond. During these visits, the PI and the PDRA will also engage in important knowledge-transfer activities with the product development teams in Microsoft.

In addition, the topics addressed in this project proposal are closely linked with the research interests of multiple scientists working in industrial research labs in North America and Europe. For instance, The PI has written a research paper with Dr. Vahab Mirrokni (Google Research, NY) in the recent past, whereas Dr. Silvio Lattanzi (Google Research, Zurich), Dr. Amir Abboud (IBM Almaden) and Dr. Krzysztof Onak (IBM Watson) have all worked on topics/problems that are directly addressed in the project proposal. In order to maximise the impact of the project, the PI will visit these industry labs to interact with the scientists working in these places and to give presentations on dynamic algorithms.

The UK is home to a large and growing data centre industry. The PI will visit the scientists working in the UK data centre companies such as British Telecom and Telehouse to participate in knowledge transfer activities. The already existing connections between the University of Warwick and the UK industries will be of great benefit to the PI in achieving this impact. The PI will use these connections by participating in knowledge-transfer activities at the Alan Turing Institute (of which Warwick was a founding member), Warwick Institute for Data Science and the CDT on Mathematics for Real-World Systems.

The research area of dynamic algorithms has been witness to a flurry of recent, exciting new developments in the theoretical computer science community. Indeed, results from this area received the best paper awards at SODA 2013 and SODA 2018, and SODA 2017 and SODA 2018 had entire sessions devoted to dynamic algorithms. In contrast, this research area is currently underrepresented in the UK academia. To address this discrepancy and to popularise the area of dynamic algorithms in the UK, the PI will organise a three day workshop towards the end of the project. The workshop will include invited talks and tutorials by the scientists working in the UK industries and experts in dynamic algorithms from all over the world. This will serve as a much needed platform for encouraging direct collaboration between academia and industry on possible applications of dynamic algorithms.