Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$35,000.00

Algorithms for changing environments

EF 2023-24

Résumé
Although countless algorithms have been developed to solve a large variety of problems, few are designed to adapt to change.  The goal of my research program is to harness the synergy between theory and practice to form practical algorithms addressing a wide variety of real-life problems arising in changing environments. As an example, consider the assignment of customers to power stations; an assignment is workable if each power station has sufficient capacity to meet the demands of all of the customers assigned to it. To rearrange customers to change from one workable assignment to another without shutting down the entire system, customers can be moved one by one, always ensuring that a move results in a workable assignment.  In this way, power can continue to flow while changes are taking place. Introduced only a decade ago, the reconfiguration framework is a natural approach for developing algorithms, as it can be used to navigate among configurations (such as workable assignments) by means of a reconfiguration sequence of steps (such as the reassignment of a single customer from one power station to another).  However, as studied thus far, reconfiguration cannot express the intricacies of many real-world problems. Moreover, even for those problems that can be expressed using the framework, such as studying the effects of gerrymandering and folding biomolecules into 2D and 3D structures, efficient algorithms are elusive; thus, reconfiguration has been under-utilized. In order to apply reconfiguration to real problems, my objectives are to (1) enrich the expressive power of reconfiguration; (2) extend the range of types of algorithms developed; and (3) develop a toolkit to apply reconfiguration to diverse problems, such as communication in a wireless network, efficient storage of code, and the rearrangement of atoms for use in quantum simulation, in collaboration with experts in various areas of computer science, including algorithm design, databases, and high-performance computing, as well as mathematicians, engineers, and physicists. Due to its newness and wide applicability, reconfiguration is an attractive area for students at all levels. An undergraduate student attempting research for the first time can quickly become sufficiently familiar with the research area of reconfiguration to start making original contributions; a graduate student can initiate work on a new branch of reconfiguration forming the foundations of their future research and career. Building bridges to other fields of study prepares students for diverse careers, as they learn the benefits of forming a network, working independently and in collaboration with others, and communicating ideas to a heterogeneous audience. By learning how to formulate new problems, work with others to find solutions, and consult with experts in diverse fields, students will be well prepared for careers in academia or any workplace in which environments are subject to change.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2022-02953
Name nom
Nishimura, Naomi
Department département
Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2022
Award amount
35000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Algorithms for changing environments
Keyword
algorithm design and analysis; computational complexity; fixed-parameter algorithms; graph algorithms; reconfiguration
Application summary
Although countless algorithms have been developed to solve a large variety of problems, few are designed to adapt to change.  The goal of my research program is to harness the synergy between theory and practice to form practical algorithms addressing a wide variety of real-life problems arising in changing environments. As an example, consider the assignment of customers to power stations; an assignment is workable if each power station has sufficient capacity to meet the demands of all of the customers assigned to it. To rearrange customers to change from one workable assignment to another without shutting down the entire system, customers can be moved one by one, always ensuring that a move results in a workable assignment.  In this way, power can continue to flow while changes are taking place. Introduced only a decade ago, the reconfiguration framework is a natural approach for developing algorithms, as it can be used to navigate among configurations (such as workable assignments) by means of a reconfiguration sequence of steps (such as the reassignment of a single customer from one power station to another).  However, as studied thus far, reconfiguration cannot express the intricacies of many real-world problems. Moreover, even for those problems that can be expressed using the framework, such as studying the effects of gerrymandering and folding biomolecules into 2D and 3D structures, efficient algorithms are elusive; thus, reconfiguration has been under-utilized. In order to apply reconfiguration to real problems, my objectives are to (1) enrich the expressive power of reconfiguration; (2) extend the range of types of algorithms developed; and (3) develop a toolkit to apply reconfiguration to diverse problems, such as communication in a wireless network, efficient storage of code, and the rearrangement of atoms for use in quantum simulation, in collaboration with experts in various areas of computer science, including algorithm design, databases, and high-performance computing, as well as mathematicians, engineers, and physicists. Due to its newness and wide applicability, reconfiguration is an attractive area for students at all levels. An undergraduate student attempting research for the first time can quickly become sufficiently familiar with the research area of reconfiguration to start making original contributions; a graduate student can initiate work on a new branch of reconfiguration forming the foundations of their future research and career. Building bridges to other fields of study prepares students for diverse careers, as they learn the benefits of forming a network, working independently and in collaboration with others, and communicating ideas to a heterogeneous audience. By learning how to formulate new problems, work with others to find solutions, and consult with experts in diverse fields, students will be well prepared for careers in academia or any workplace in which environments are subject to change.