CMPUT 675 - Topics in Combinatorics and Optimization

Overview

The main emphasis of algorithm design is to be more clever than brute-force search. For example, there are often exponentially many paths between two vertices in a graph. Despite this, one can find the shortest path in polynomial time by leveraging the structure of the problem. Many of these important algorithms are covered in undergraduate classes, but what can we do beyond these basic results?

We will further explore what combinatorial problems can be solved (or "nearly solved") in polynomial time, we will see algorithms for classic problems that run faster than "textbook" algorithms, and we will explore connections between combinatorics and convex optimization.

Objectives

• Understand faster algorithms for classic optimization problems.
• Study discrete optimization in general contexts: matroids, submodular functions, generalizations of network flow.
• See connections between linear/semidefinite programming and combinatorial optimization.

Course Work

• Scribe notes
• Assignments
• Final project