Contact the Faculty of Science


Zachary Friggstad, PhD

Assistant Professor


Computing Science

About Me


  • 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.