EPSRC logo

Details of Grant 

EPSRC Reference: EP/S03353X/1
Title: Theory and Applications of Dynamic Algorithms
Principal Investigator: Bhattacharya, Dr S
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Microsoft
Department: Computer Science
Organisation: University of Warwick
Scheme: New Investigator Award
Starts: 24 February 2020 Ends: 23 February 2023 Value (£): 246,483
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:
Panel DatePanel NameOutcome
02 May 2019 EPSRC ICT Prioritisation Panel May 2019 Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.warwick.ac.uk