Grant: Discovery Grants Program - Individual
Ryerson University
$26,000.00
Efficiency Tradeoffs for Combinatorial Optimization Problems
FY 2020-21
Summary
One of the fundamental subjects in Theoretical Computer Science is the study of computation capabilities when resources are limited. Indeed, many real-life optimization problems admit easy-to-describe and non-efficient algorithmic solutions if one assumes unlimited computation power, e.g. no restrictions in time, and full coordination of participating processes. How well can such a problem be solved when one is restricted to use efficient algorithms with limited resources?
When the limited resource is time, i.e. the number of computation steps, Theoretical Computer Science has provided a rich problem classification mostly based on deep and unresolved mathematical conjectures. According to these conjectures, a large family of combinatorial optimization problems cannot be solved exactly and efficiently, and as such one is bound to provide only approximate solutions within reasonable time. Surprisingly, a restricted and systematic algorithmic technique, based on the so-called mathematical tool of convex-programming, has given remarkable positive results in this direction. Recently, this algorithmic technique has been leveraged into a dynamic model of computation where one can provably trade efficiency for accuracy. Half of the current program will investigate the capabilities of this model of computation for the whole spectrum of efficiency notions, touching and extending on the computability predictions of famous mathematical conjectures, e.g. that of ``P is not equal to NP'' and the Unique Games Conjecture. Progress in this research program will enhance our understanding of the solvability of hard combinatorial optimization problems, will result into new algorithmic techniques, as well as will identify structural properties of input instances that are difficult to solve.
Other valuable computation resources in real-life problems include the centrality of computation. For example, this is the case in the so-called search-and-fetch problems that abound in search-and-rescue operations. Indeed, recent developments in modern robotics give rise to combinatorial problems in which a number of autonomous mobile agents (drones) attempt to complete a task, e.g. locate and rescue a victim in an unknown environment. Computation in these cases is ``distributed'' among the participating mobile agents, while the centrality of computation is affected by the communication capabilities of the robots. The other half of the current research program will investigate the computation capabilities of mobile agents in search-and-fetch problems. The focus of this research will be on efficiency tradeoffs for a large spectrum of centrality notions as it is imposed by different robot communication capabilities. Progress in this area will have immediate impact to robotics applications, as well as it will deepen our understanding of the computation capabilities in distributed systems.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-04312
Name nom
Georgiou, Konstantinos
Department département
Mathematics
Organization id
43
Institution établissement
Ryerson University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
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
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
Installment
inst:5-6
Partie
2
Nb partie
6
Application title
Efficiency Tradeoffs for Combinatorial Optimization Problems
Keyword
NSERC
Application summary
One of the fundamental subjects in Theoretical Computer Science is the study of computation capabilities when resources are limited. Indeed, many real-life optimization problems admit easy-to-describe and non-efficient algorithmic solutions if one assumes unlimited computation power, e.g. no restrictions in time, and full coordination of participating processes. How well can such a problem be solved when one is restricted to use efficient algorithms with limited resources?
When the limited resource is time, i.e. the number of computation steps, Theoretical Computer Science has provided a rich problem classification mostly based on deep and unresolved mathematical conjectures. According to these conjectures, a large family of combinatorial optimization problems cannot be solved exactly and efficiently, and as such one is bound to provide only approximate solutions within reasonable time. Surprisingly, a restricted and systematic algorithmic technique, based on the so-called mathematical tool of convex-programming, has given remarkable positive results in this direction. Recently, this algorithmic technique has been leveraged into a dynamic model of computation where one can provably trade efficiency for accuracy. Half of the current program will investigate the capabilities of this model of computation for the whole spectrum of efficiency notions, touching and extending on the computability predictions of famous mathematical conjectures, e.g. that of ``P is not equal to NP'' and the Unique Games Conjecture. Progress in this research program will enhance our understanding of the solvability of hard combinatorial optimization problems, will result into new algorithmic techniques, as well as will identify structural properties of input instances that are difficult to solve.
Other valuable computation resources in real-life problems include the centrality of computation. For example, this is the case in the so-called search-and-fetch problems that abound in search-and-rescue operations. Indeed, recent developments in modern robotics give rise to combinatorial problems in which a number of autonomous mobile agents (drones) attempt to complete a task, e.g. locate and rescue a victim in an unknown environment. Computation in these cases is ``distributed'' among the participating mobile agents, while the centrality of computation is affected by the communication capabilities of the robots. The other half of the current research program will investigate the computation capabilities of mobile agents in search-and-fetch problems. The focus of this research will be on efficiency tradeoffs for a large spectrum of centrality notions as it is imposed by different robot communication capabilities. Progress in this area will have immediate impact to robotics applications, as well as it will deepen our understanding of the computation capabilities in distributed systems.