| EPSRC Reference: |
EP/S03353X/1 |
| Title: |
Theory and Applications of Dynamic Algorithms |
| Principal Investigator: |
Bhattacharya, Dr S |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| 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: |
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
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 |