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