Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McMaster University

$27,000.00

Algorithmic and game-theoretic analysis and implementation of network design

FY 2011-12

Summary
Network problems are among the most basic optimization problems. Whether the goods transfered through them are data or commodities they must be designed so as to optimize metrics such as time, costs, or revenue. It has been long known that although these networks may be very different, their modelling can capture their underlying common characteristics. A very recent manifestation of this trend (alongside the older examples of network flow, routing, fault tolerance etc.) is the introduction of selfish behaviour in the study of large data and communication networks such as the Internet; while this is a new paradigm for most computer scientists, it has been studied for more than 50 years by economists and the transportation community. The design of network protocols based on auction mechanism design is another such example. The purpose of this research is to explore the application of these new paradigms in network design from an algorithmic point of view, alongside the study of more `traditional' aspects such as the development, analysis and implementation of better approximation algorithms for network flow and routing problems. In a world that is more inter-connected than ever, the expectation of this research proposal is to have a significant impact on the more efficient distribution of information, goods, services etc.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
262124-2007
Name nom
Karakostas, George
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2007
Award amount
27000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
800
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information and communication services
Area of application fr
Services d'information et de télécommunications
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
5
Nb partie
5
Application title
Algorithmic and game-theoretic analysis and implementation of network design
Keyword
NSERC
Application summary
Network problems are among the most basic optimization problems. Whether the goods transfered through them are data or commodities they must be designed so as to optimize metrics such as time, costs, or revenue. It has been long known that although these networks may be very different, their modelling can capture their underlying common characteristics. A very recent manifestation of this trend (alongside the older examples of network flow, routing, fault tolerance etc.) is the introduction of selfish behaviour in the study of large data and communication networks such as the Internet; while this is a new paradigm for most computer scientists, it has been studied for more than 50 years by economists and the transportation community. The design of network protocols based on auction mechanism design is another such example. The purpose of this research is to explore the application of these new paradigms in network design from an algorithmic point of view, alongside the study of more `traditional' aspects such as the development, analysis and implementation of better approximation algorithms for network flow and routing problems. In a world that is more inter-connected than ever, the expectation of this research proposal is to have a significant impact on the more efficient distribution of information, goods, services etc.