Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$42,000.00

Flexible and Effective Techniques for the Design of Approximation Algorithms

FY 2015-16

Summary
Discrete optimization problems are abundant in everyday life, and arise whenever complex decisions about the efficient distribution of scarce resources have to be made. There is a plethora of such problems, including the timely scheduling of trains in a local transit network, and the optimal layout of wires in the VLSI design phase of a modern chip. In these two examples, and in general, relevant practical instances are often NP-hard, and thus intractable. This proposal focuses on the design of Approximation Algorithms that efficiently compute near-optimal solutions to given optimization problems. Emphasis will be placed on the systematic use of mathematical programming (MP) in the design of such algorithms. MP is an important tool in the development of approximation algorithms. Starting from a mathematical model of a problem, one typically first derives a strong and tractable relaxation, solves it, and ultimately rounds its solution into one that is feasible for the original problem. The performance ratio of such an algorithm chiefly depends on two main factors: the quality of the MP relaxation, and the rounding method. While several powerful and general purpose methods for the above rounding process have been developed in the last 30 years, the following meta question (paraphrased from Vazirani's book) remains: Given a strong MP relaxation, is there always a way of rounding it into a good solution for the underlying optimization problem? Shedding light on this question is the long-term goal of my research. More explicitly, in my research program I intend to systematically study the use of strong MP relaxations in the design of approximation algorithms. I give three examples of ongoing projects together with several example short-term goals. The proposed research objectives are central in Combinatorial Optimization and Theoretical Computer Science; progress made is anticipated to have significant direct impact in these fields, and in practical applications of MP. The proposed research program is a natural continuation of existing work, and it will continue to attract excellent students.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
288340-2012
Name nom
KËnemann, Jochen
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2012
Award amount
42000
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
4
Nb partie
5
Application title
Flexible and Effective Techniques for the Design of Approximation Algorithms
Keyword
NSERC
Application summary
Discrete optimization problems are abundant in everyday life, and arise whenever complex decisions about the efficient distribution of scarce resources have to be made. There is a plethora of such problems, including the timely scheduling of trains in a local transit network, and the optimal layout of wires in the VLSI design phase of a modern chip. In these two examples, and in general, relevant practical instances are often NP-hard, and thus intractable. This proposal focuses on the design of Approximation Algorithms that efficiently compute near-optimal solutions to given optimization problems. Emphasis will be placed on the systematic use of mathematical programming (MP) in the design of such algorithms. MP is an important tool in the development of approximation algorithms. Starting from a mathematical model of a problem, one typically first derives a strong and tractable relaxation, solves it, and ultimately rounds its solution into one that is feasible for the original problem. The performance ratio of such an algorithm chiefly depends on two main factors: the quality of the MP relaxation, and the rounding method. While several powerful and general purpose methods for the above rounding process have been developed in the last 30 years, the following meta question (paraphrased from Vazirani's book) remains: Given a strong MP relaxation, is there always a way of rounding it into a good solution for the underlying optimization problem? Shedding light on this question is the long-term goal of my research. More explicitly, in my research program I intend to systematically study the use of strong MP relaxations in the design of approximation algorithms. I give three examples of ongoing projects together with several example short-term goals. The proposed research objectives are central in Combinatorial Optimization and Theoretical Computer Science; progress made is anticipated to have significant direct impact in these fields, and in practical applications of MP. The proposed research program is a natural continuation of existing work, and it will continue to attract excellent students.
University of Waterloo - $42,000 Grant (2015-16) | Canada Spends