CMPUT 675 - Combinatorial Optimization
Overview
Combinatorial optimization problems concern minimizing or maximizing an objective function when some or all of the variables are discrete. Classic examples include shortest path, minimum cut, minimum spanning tree, knapsack, etc. These problems frequently arise when there are boolean decisions to be made: Should I include this edge in my matching? Should I choose to schedule a job at this time?
This course covers various algorithmic techniques for solving combinatorial optimization problems. Particular emphasis will be placed on network flow, matchings, convex optimization (linear and semidefinite programming and their applications to discrete optimization), and matroids. Throughout, min-max relationships will be highlighted (eg. max flow/min cut, LP duality, Tutte’s matching theorem, perfect graphs) and will often drive the design of the algorithms we study.
The style of the course is like an algorithms course. We will discuss and prove properties and algorithms for solving optimization problems. Assignments will typically ask students to design and prove correctness of an algorithm, prove mathematical properties of problems, generate counter examples to some claims, and occasionally trace the execution of an algorithm on paper. There is no programming component in this course.
Objectives
- Understand the underlyingprinciples behind a large class of discrete optimization problems
- Learn to apply convex optimization problem to solve problems in combinatorial optimization
- Design algorithms to solve a broad range of combinatorial optimization problems
- Become familiar with how matroids can be used to model and solve various problems
Course Work
- Bi-weekly assignments (written)
- Producing scribe notes for up to 2 lectures
- Take-home final exam (offline)
Related Research Areas
- Approximation Algorithms
- Graph Theory
- Convex Optimization