Discovery Projects - Grant ID: DP210103849

Funding Activity

Website
http://dataportal.arc.gov.au/NCGP/Web/Grant/Grant/DP210103849

Funding Status
Active

Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the .

Funded Activity Summary

Improved algorithms via random sampling. Randomized methods have recently come into the spotlight when it comes to solving computationally "intractable" subset problems. The running time of a range of algorithms has been improved by replacing their first steps by a simple method of adding to the solution a small subset uniformly at random, and repeating the process many times. This project will explore various other ways how (not necessarily uniform) random sampling can improve the running time of algorithms; and explore the analysis of polynomial-time randomized algorithms. The project will focus on cycle cutsets and domination problems that have applications in operating systems, chip design and verification, facility location, and surveillance and monitoring.

Funded Activity Details

Start Date: 01-07-2021

End Date: 30-06-2024

Funding Scheme: Discovery Projects

Funding Amount: $435,346.00

Funder: Australian Research Council

Research Topics

ANZSRC Field of Research (FoR)

Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) | Analysis of Algorithms and Complexity | Computation Theory and Mathematics

ANZSRC Socio-Economic Objective (SEO)

Expanding Knowledge in the Information and Computing Sciences | Expanding Knowledge in the Mathematical Sciences |

Other Keywords

Analysis of Algorithms and Complexity | Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) | Computation Theory and Mathematics | Expanding Knowledge in the Information and Computing Sciences | Expanding Knowledge in the Mathematical Sciences

Related Links