Zachary Friggstad, PhD
Associate Professor, Faculty of Science - Computing Science
- B.Sc, Computing Science, University of Lethbridge, 2005
- M.Sc, Computing Science, University of Alberta, 2007
- Ph.D., Computing Science, University of Alberta, 2011
Discrete Optimization, Approximation Algorithms, Mathematical Programming.
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.
This topics course is designed for new course offerings that may be offered in a given term. Prerequisites are determined by the instructor in the course outline. See Note (3) above.
The essence of computing science is in solving problems by computation. This course is interested in algorithmic problems that can be solved within at most several hours by well prepared people, where a solution involves properly understanding a written description, designing an efficient algorithm to solve the problem, and then correctly implementing the solution. Prerequisites: CMPUT 204 and any 300-level Computing Science course, or consent of the instructor.
This topics course is designed for a one on one individual study course between a student and an instructor. Prerequisites are determined by the instructor in the course outline. See Note (3) above.