Grant: Discovery Grants Program - Individual
Simon Fraser University
$17,000.00
Algorithms for combinatorial optimization
EF 2009-10
Résumé
The aim of this project is to find efficient algorithms for combinatorial optimization problems. These problems arise in both theoretical and applied settings. The most famous problem of this type is the Travelling Salesman Problem, but many combinatorial optimization problems are linked through beautiful theory and common ideas. Combinatorial optimization problems are characterized by having a discrete search space. The challenge is that this space is nevertheless too large to enumerate completely, even with very fast computers, so intelligent algorithms and heuristics are required. Our aim is to find and analyze such algorithms.
This proposal focuses on four particular combinatorial questions. They are:
1. Finding algorithms for the colourful linear programming feasibility problem.
2. Studying algorithms for generating monotone boolean functions and applying these algorithms to understanding metabolic networks.
3. Using a distributional approach to analyze combinatorial objective functions defined on groups.
4. Proving the Grone-Merris conjecture on the spectrum of graphs.
Besides their immediate application, progress on these nice problems will help to illuminate key issues in optimization.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
341698-2007
Name nom
Stephen, Tamon
Department département
Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2007
Award amount
17000
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
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
Area of application code
802
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 systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
3
Nb partie
5
Application title
Algorithms for combinatorial optimization
Keyword
NA
Application summary
The aim of this project is to find efficient algorithms for combinatorial optimization problems. These problems arise in both theoretical and applied settings. The most famous problem of this type is the Travelling Salesman Problem, but many combinatorial optimization problems are linked through beautiful theory and common ideas. Combinatorial optimization problems are characterized by having a discrete search space. The challenge is that this space is nevertheless too large to enumerate completely, even with very fast computers, so intelligent algorithms and heuristics are required. Our aim is to find and analyze such algorithms.
This proposal focuses on four particular combinatorial questions. They are:
1. Finding algorithms for the colourful linear programming feasibility problem.
2. Studying algorithms for generating monotone boolean functions and applying these algorithms to understanding metabolic networks.
3. Using a distributional approach to analyze combinatorial objective functions defined on groups.
4. Proving the Grone-Merris conjecture on the spectrum of graphs.
Besides their immediate application, progress on these nice problems will help to illuminate key issues in optimization.