Grant: Discovery Grants Program - Individual
University of Waterloo
$26,000.00
Algorithms that handle change over time and space
EF 2018-19
Résumé
My goal over the next five years is to understand how algorithms can be designed to accommodate change, where change can take place before, during, or after a problem is solved. Depending on when the change occurs, it might result in modifications to the original input or in multiple solutions to a single input. The type of change can be either inherent in or external to the problem and the inputs. The areas of parameterized complexity and reconfiguration lend themselves well to investigations of approaches to solving problems in such settings.*As a real-life example, repairs to power stations might require change between two good placements of customers, placements in which the output of each station is sufficient to meet the needs of all customers it serves. To minimize disruption of service, customers are moved one by one, each change resulting in a good assignment. In general, reconfiguration models changes that occur after a problem has been solved; solutions to a specific input (here, good assignments) can be viewed as vertices in a reconfiguration graph, where an edge indicates that one solution can be transformed into another in a single step, for some definition of a step. Recent research results have considered various properties of the reconfiguration graph, such as connectivity and diameter, and include the problem of determining whether there is a path from solution S to solution T (known as S-T connectivity). *A natural setting for the study of change is the framework of parameterized complexity. Here, one identifies parameters of a problem and attempts to develop an algorithm running in time polynomial in the size of the input but subject to a potentially larger function of the parameters. This approach can yield practical algorithms for otherwise intractable problems in situations when the parameters are small, or demonstrate that such algorithms are unlikely to exist. Parameters can measure how much inputs can differ, how much change can be allowed, or how much solutions can vary for cases in which change occurs before, during, or after a problem is solved, respectively. My recent results combine reconfiguration and parameterized complexity; here parameters under consideration include the length of the transformation from one solution into another, bounds on the sizes of solutions, and properties of the inputs.*My two-fold approach to the study of change encompasses both general properties of classes of problems and results optimized for specific settings chosen from a wide spectrum of diverse application areas, such as fundamental problems with applications to biology, voting protocols, and communication and social networks. I plan to form a unified framework of models that captures change in both inputs and outputs. Examination of the parameterized complexity of such models may yield practical solutions to real-life problems as well as a general understanding about the nature of change.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2016-03621
Name nom
Nishimura, Naomi
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2016
Award amount
26000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à 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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
3
Nb partie
5
Application title
Algorithms that handle change over time and space
Keyword
NSERC
Application summary
My goal over the next five years is to understand how algorithms can be designed to accommodate change, where change can take place before, during, or after a problem is solved. Depending on when the change occurs, it might result in modifications to the original input or in multiple solutions to a single input. The type of change can be either inherent in or external to the problem and the inputs. The areas of parameterized complexity and reconfiguration lend themselves well to investigations of approaches to solving problems in such settings.*As a real-life example, repairs to power stations might require change between two good placements of customers, placements in which the output of each station is sufficient to meet the needs of all customers it serves. To minimize disruption of service, customers are moved one by one, each change resulting in a good assignment. In general, reconfiguration models changes that occur after a problem has been solved; solutions to a specific input (here, good assignments) can be viewed as vertices in a reconfiguration graph, where an edge indicates that one solution can be transformed into another in a single step, for some definition of a step. Recent research results have considered various properties of the reconfiguration graph, such as connectivity and diameter, and include the problem of determining whether there is a path from solution S to solution T (known as S-T connectivity). *A natural setting for the study of change is the framework of parameterized complexity. Here, one identifies parameters of a problem and attempts to develop an algorithm running in time polynomial in the size of the input but subject to a potentially larger function of the parameters. This approach can yield practical algorithms for otherwise intractable problems in situations when the parameters are small, or demonstrate that such algorithms are unlikely to exist. Parameters can measure how much inputs can differ, how much change can be allowed, or how much solutions can vary for cases in which change occurs before, during, or after a problem is solved, respectively. My recent results combine reconfiguration and parameterized complexity; here parameters under consideration include the length of the transformation from one solution into another, bounds on the sizes of solutions, and properties of the inputs.*My two-fold approach to the study of change encompasses both general properties of classes of problems and results optimized for specific settings chosen from a wide spectrum of diverse application areas, such as fundamental problems with applications to biology, voting protocols, and communication and social networks. I plan to form a unified framework of models that captures change in both inputs and outputs. Examination of the parameterized complexity of such models may yield practical solutions to real-life problems as well as a general understanding about the nature of change.