Grant: Discovery Grants Program - Individual
University of Alberta
$23,000.00
Improved Mathematical Programming Techniques for Approximation Algorithms
FY 2018-19
Summary
A striking number of problems in discrete optimization are, unfortunately, computationally intractable. These problems stem from issues faced by our complex society: coordinating vehicles in a transportation network, compiling code to create efficient executable programs, determining placements of fire or ambulance stations to improve response time. More precisely, many such problems are NP-hard meaning we do not have, nor do we expect, any efficient algorithms to solve these problems optimally. To cope with this difficulty, we focus on devising efficient algorithms that find near-optimum solutions.*The subject of this proposal is designing improved approximation algorithms for NP-hard optimization problems, primarily by devising and analyzing new mathematical programming approaches. The goal is to provide new polynomial-time algorithms to compute solutions whose costs are within some proven explicit bound of the optimum solution. The fact that these algorithms will be based on mathematical programs will also help articulate the connection between theoretical computing science and practical heuristics, as linear and integer programming techniques are often used to devise algorithms that perform well experimentally yet lack proven guarantees on their worst-case performance.*My proposed research includes modelling discrete optimization problems as mathematical programs and then relaxing some constraints of these programs to get models that can be solved efficiently. Typically, this is a linear or semidefinite programming relaxation of an integer program. Once this relaxation is solved, the solutions are carefully rounded in a way that obtains a feasible solution to the original model while preserving the objective function value as much as possible. This is already known to be one of the most effective ways to design approximation algorithms; eight chapters of the recent book ""The Design of Approximation Algorithms"" by Shmoys and Williamson are devoted to this method.*In particular, applications of mathematical programming techniques to vehicle routing and resource allocation problems will be investigated. In vehicle routing problems, a strong linear programming approach has recently proven useful in addressing problems with multiple vehicles and I propose to further explore these techniques to address fundamental routing problems. Additionally, I will investigate the so-called unsplittable flow problem in trees which represents the frontier of our understanding in how to approximate resource allocation and packing problems. In particular, I expect that understanding the effectiveness of a relatively new linear programming model should either lead to improved approximations or tighter lower bounds.*
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-06496
Name nom
Friggstad, Zachary
Department département
Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2015
Award amount
23000
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
4
Nb partie
5
Application title
Improved Mathematical Programming Techniques for Approximation Algorithms
Keyword
NSERC
Application summary
A striking number of problems in discrete optimization are, unfortunately, computationally intractable. These problems stem from issues faced by our complex society: coordinating vehicles in a transportation network, compiling code to create efficient executable programs, determining placements of fire or ambulance stations to improve response time. More precisely, many such problems are NP-hard meaning we do not have, nor do we expect, any efficient algorithms to solve these problems optimally. To cope with this difficulty, we focus on devising efficient algorithms that find near-optimum solutions.*The subject of this proposal is designing improved approximation algorithms for NP-hard optimization problems, primarily by devising and analyzing new mathematical programming approaches. The goal is to provide new polynomial-time algorithms to compute solutions whose costs are within some proven explicit bound of the optimum solution. The fact that these algorithms will be based on mathematical programs will also help articulate the connection between theoretical computing science and practical heuristics, as linear and integer programming techniques are often used to devise algorithms that perform well experimentally yet lack proven guarantees on their worst-case performance.*My proposed research includes modelling discrete optimization problems as mathematical programs and then relaxing some constraints of these programs to get models that can be solved efficiently. Typically, this is a linear or semidefinite programming relaxation of an integer program. Once this relaxation is solved, the solutions are carefully rounded in a way that obtains a feasible solution to the original model while preserving the objective function value as much as possible. This is already known to be one of the most effective ways to design approximation algorithms; eight chapters of the recent book ""The Design of Approximation Algorithms"" by Shmoys and Williamson are devoted to this method.*In particular, applications of mathematical programming techniques to vehicle routing and resource allocation problems will be investigated. In vehicle routing problems, a strong linear programming approach has recently proven useful in addressing problems with multiple vehicles and I propose to further explore these techniques to address fundamental routing problems. Additionally, I will investigate the so-called unsplittable flow problem in trees which represents the frontier of our understanding in how to approximate resource allocation and packing problems. In particular, I expect that understanding the effectiveness of a relatively new linear programming model should either lead to improved approximations or tighter lower bounds.*