Zachary Friggstad, PhD
Contact
Associate Professor, Faculty of Science - Computing Science
- zacharyf@ualberta.ca
Overview
About
Education
- B.Sc, Computing Science, University of Lethbridge, 2005
- M.Sc, Computing Science, University of Alberta, 2007
- Ph.D., Computing Science, University of Alberta, 2011
Research
Area
Algorithmics
Interests
Discrete Optimization, Approximation Algorithms, Mathematical Programming.
Summary
I design algorithms for discrete optimization problems. Common examples include vehicle routing, facility placement, resource allocation, and job scheduling problems.
Many of these problems are NP-hard. This means we do not expect any algorithm is able to efficiently find optimum solutions to these problems. I cope with this difficulty by designing approximation algorithms: algorithms that find near-optimum solutions. These are not just heuristics that tend to perform well in experiments. Such algorithms come with a proven guarantee on how far their computed solutions can deviate from the optimum solution.
Often, but not exclusively, I consider tractable convex relaxations of these problems such as linear or semidefinite programming relaxations. The goal is then to find such a relaxation that represents the original problem with high fidelity.