Zachary Friggstad, PhD

Email

zacharyf@ualberta.ca

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

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.