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.
The second course of a two-course sequence on algorithm design. Emphasis on principles of algorithm design. Categories of algorithms such as divide-and-conquer, greedy algorithms, dynamic programming; analysis of algorithms; limits of algorithm design; NP-completeness; heuristic algorithms. Prerequisites: CMPUT 204; one of STAT 141, 151, 235 or 265 or SCI 151; one of MATH 225, 227, 228; or consent of the instructor.Fall Term 2021
The essence of computing science is in solving problems by computation. It may take anywhere from several minutes to several years from the initial posing of a problem specification to finally getting a working program. This course is interested in problems that can be solved within at most several hours by well prepared people. Prerequisites: Restricted to students participating in the programming contest. Any 300-level course, and consent of the instructor.Winter Term 2022