Course Information
Instructor: Zachary Friggstad
Contact Information: click here
Lecture: MWF 1:001:50pm in CSC B41
Office Hours: Tuesday 1:001:50pm, Wednesday 2:00  2:50 in ATH 306
Outline
One of the main goals of algorithm design is to be more clever than bruteforce 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.
Background
Students are expected to have a background in algorithms at the level of a 3rd year undergraduate course. You should know what a graph is, but most concepts will be reviewed as we proceed. Basic linear algebra is also required.
References
There is no required textbook. Lectures notes will be provided throughout the term. Additional resources that may help supplement the notes or provide more information on related topics are listed at the bottom of this page .
Topics
The course consists mostly of core concepts but there may be time for some extra topics. A list of topics that will be covered follows. Click on an entry for a brief summary.
 Matchings
Maximum cardinality matchings (bipartite and general); minimumweight perfect matchings; certificates of optimality.
 Flows and Cuts
Single commodity flows; maxflow/mincut theorem; circulations; Hoffman's circulation theorem; minimumcost flows; GomeryHu trees.
 Matroids
A generalization of the seemingly unrelated concepts of spanning trees and linear independence for vector spaces. If a problem admits a matroid structure, then some optimization tasks to be performed efficiently.
 Convex Optimization
A discrete optimization problem can usually be cast as an integer or quadratic program. These are NPhard to solve, but their linear or semidefinite relaxations can be solved optimally in polynomial time. This can be helpful in designing efficient exact or approximation algorithms.
Topics: the ellipsoid method, separation oracles, geometry of polyhedra, linear programming duality.  Integral Polytopes
With many problems we can solve in polynomial time, we can write a linear program whose optimum solutions turn out to be integral. This is also useful for designing approximation algorithms. We will explore total unimodularity and the uncrossing technique.
 Perfect Graphs
Perfect graphs generalize many graph classes for which we know how to solve some NPhard problems in polynomial time. We can colour perfect graphs with the fewest possible colours in polynomial time, but the only techniques known (so far) use semidefinite programming. Their independent sets also have a very interesting polyhedral characterization.
 Submodular Optimization
Classic optimization problems ask for a minweight or maxvalue feasible set. Usually these are the sums of weights/values of individual items. A submodular function generalizes this: values of solutions satisfy a "diminishing returns" property. We can find a minimizer of a submodular function in polynomial time. A maximizer is hard to find, but simple approximation algorithms are known.
 Approximation Algorithms
Though the main emphasis is on designing polynomialtime algorithms to solve problems exactly, we will see a few approximation algorithms along the way (algorithms that find provably nearoptimum solutions to NPhard problems). There will be only miniscule overlap with my previous course on approximation algorithms .
Extra topics may include the following. Surely we cannot cover all, but we can decide as a class as we go. Anything we do not cover would make for a good project topic.
 Randomized Algorithms
Faster and/or simpler randomized algorithms for classic problems: minimum spanning trees, global minimum cuts, perfect matchings in general graphs.
 EdgeBased Version of Hex
A popular game in our department is hex which can be generalized as follows: given a graph $G=(V,E)$ with two nodes $s,t \in V$, players alternate by placing stones on empty nodes (player 1 = black, player 2 = white) on the nodes in $V\{s,t\}$. Black's goal is to ensure there is an $st$ path whose intermediate nodes have a black stone, white's goal is to prevent this.
Determining who will win if both players play optimally is a PSPACEcomplete problem. But if the players place stones on the edges and black's goal is to connect $s$ and $t$ using edges with black stones, we can determine who will win in polynomial time.  Planar Graphs
 Finding a maximum cut or (uniform) sparsest cut in polynomial time.
 The planar separator theorem: how to split a planar graph into two roughly equal size parts while deleting only $O(\sqrt V)$ nodes. Applications to simple approximation schemes for NPhard problems.
 Multicommodity flow/cut gap and KleinPlotkinRao decompositions.
 The OkamuraSeymour theorem for integral multicommodity flows.
 Counting Problems
We can calculate the number of spanning trees in a graph in and the number of shortest paths between two vertices polynomial time. But we cannot count the number of perfect matchings in even a bipartite graph unless P = NP.
We can, however, efficiently estimate the number of perfect matchings within arbitrary precision with a randomized approximation scheme. We can also count the number of perfect matchings in a planar graph in polynomial time.  LiftandProject Techniques
A recentlypopular method for strengthening convex relaxations of discrete optimization problems is the liftandproject technique. Additional constraints and variables are added to an LP or SDP in a way such that the projection of the feasible solutions back to the original variables tightenes the set of feasible solutions around the convex hull of integer solutions.
Sometimes this can be used to get integral polytopes for some problems, more commonly it is used to get better approximation algorithms. We could discuss the basics of the SheraliAdams or SumofSquares technique.
Grading
Assignments  60%
There will be 5 assignments in total, each worth 12%. You will have 2 weeks to complete each assignment. Each assignment will be due on a Wednesday and must be handed in at the start of the lecture.
Scribe Notes  15%
Students will take turns recording notes from each lecture and typesetting them in LaTeX. Any details that were omitted or glossed over must be filled in. The notes will be due exactly one week after the start of the lecture (i.e. at 1pm 7 days later). These will be posted on this page for others to reference. I will provide a .tex template and notes from the first lecture.
Some details during the lecture might be glossed over. You should fill out these missing details, the goal of the notes is to be a selfcontained description of the lecture topic. I might edit the notes, but I will check with you regarding any edits I make before posting.
Final Project  25%
Deliver a presentation on a topic of your choice that is relevant to this class. More information will be made available by Oct 15 on this page, including a list of suggested topics. We will find a time during the final exam period (Dec 921) to give the presentations.
Grade Cutoffs
A ≥ 80% > B ≥ 70% > C ≥ 60% > D ≥ 50% > F
Lecture Notes
You can download the .tex template here (.pdf version and the figure).
On a lab machine, you can compile the document with pdflatex <filename>
(you can omit .tex
from the filename).
A quick LaTeX tutorial.
References: KV  Korte & Vygen
Lecture #  Topic  Scribe  Additional Reference 

1  Introduction, Bipartite Matching  Zac Friggstad 
KV 10.1
The presentation here is different than our approach in class. They build their results on top of "network flow" results, which we will get to soon. So this will be a helpful alternative view once we cover a bit more material.

2  Network Flow, MaxFlow/MinCut  Bradley Hauer 
KV 8.1
Interesting note: exercise 2 in Chapter 8 of KV shows that the FordFulkerson algorithm may never terminate if capacities are irrational.

3  Efficient Flows  Chris Martin  KV 8.3 
4  PushRelabel Analysis  Zac Friggstad  KV 8.5 
5  Undirected Cuts and GomeryHu Trees  Zac Friggstad  KV 8.6 
6  GomeryHu Trees cont.  Mirmahdi Rahgoshay  KV 8.6 
7  Graph Potentials and MinimumCost Flows  Zac Friggstad 
KV 7.1, 9.1, 9.2
The relevant part of 7.1 is Theorem 7.7. The presentation in 9.1 and 9.2 is for a slightly different version of the flow problem that is more like a minimumcost transshipment (using our terminology). But the two are easily seen to be
equivalent views (based on the connection between max flow and transshipments/bflows).

8  MinimumCost Flows via Augmenting Paths  Zac Friggstad  KV 9.2 9.4 
9  The Minimum Mean Cycle Cancelling Algorithm  Jacob Denson 
KV 9.3
The textbook has an even faster algorithm for computing minimumratio cycles
in \(O(nm)\) time. It uses the table of distances calculated by the BellmanFord algorithm
in a more clever way.

10  The Minimum Mean Cycle Cancelling Algorithm cont. and Matchings in General Graphs  Arnoosh Golestanian  KV 9.3, 10.3 
11  Matchings in General Graphs  Bradley Hauer  KV 10.5 
12  Matchings in General Graphs (wrapup)  Zac Friggstad 
KV 10.5
We settled for a slower algorithm than the textbook presents.
If you liked this topic, give the full algorithm in the textbook a read. It is fascinating :)

13  Edmond'sGallai Decompositions, Linear Programming Intro  Chris Martin  KV 10.5, 3.1 
14  Linear Programming  Huijuan Wang  KV 3.1 
15  Linear Programming (continued)  Mirmahdi Rahgoshay  
16  Totally Unimodular Matrices and Network Matrices  Arnoosh Golestanian  KV 5.4 
17  LP Duality  Zac Friggstad  KV 3.4 
18  Farkas Lemma and Strong Duality Proof  Zac Friggstad  
19  Weighted Bipartite Matching  Zac Friggstad 
KV 11.1
The textbook simply describes how to use mincost flow to solve the problem.
Here, we discussed a much simpler to implement approach that avoids the use of
complicated heaps. It runs just as fast in dense graphs.

20  Spanning Tree and Arborescence LPs  Jacob Denson 
KV 6.1, 6.2, 6.3
Our approach to showing the LP optimum value equals the integer optimum was different.
We didn't explicitly argue that all corners of the polyhedra are integral, but it wouldn't take much
more effort with the observation any objective function has an integer optimum ==> the extreme points are integral
(Theorem 5.13 in KV).

2123  The Ellipsoid Method  Zac Friggstad  KV 4.4 
24  Solving LPs via Separation Oracles  Huijuan Wang 
KV 4.2, 4.6
This was mostly an overview, the lowlevel details were skipped for the
approach to solving the weak optimization problem using separation oracles.
Most details can be found in KV 4.6, and the last missing details can be found
in the book referenced in the lecture notes.

25  Weighted Perfect Matching in General Graphs  Mirmahdi Rahgoshay 
KV 11.5
Our proof was much different than the text. See the text for an alternative approach.

26  Introduction to Matroids  Bradley Hauer  KV 13.1, 13.4 
27  Greedy Algorithm and Matroid Intersection  Chris Martin  KV 13.4, 13.5 
28  Matroid Intersection and Partitioning  Huijuan Wang  KV 13.5, 13.6 
29  Matroid Polytopes  Jacob Denson 
KV 13.4, 13.5
The proof we saw (and that is recorded in the notes) is much different than the proof in the referenced textbook.

30  Submodular Functions  Arnoosh Golestanian  
31  Submodular Function Optimization (notes soon)  Zachary Friggstad  
32  Semidefinite Programming and Max Cut  Huijuan Wang  KV 16.2 
3334  Perfect Graphs  Zachary Friggstad  
35  Counting Spanning Trees (notes soon)  Zachary Friggstad  
36  Counting Perfect Matchings in Planar Graphs (notes soon)  Zachary Friggstad 
Assignments
Each marked assignment is due on a Wednesday and must be handed in by the start of the lecture on the due date. Assignment #0 is optional, but you can try it to get a sense of the style of questions to expect and how I evaluate your work. I will mark it within 3 days of you handing it back, as long as this is before assignment #1 is due.
Suggestions
Messy and rambling solutions are difficult to read, it may be hard to assign full marks even if the solution is ultimately correct. A good solution is precise, neat, and to the point. I strongly encourage you to use LaTeX to present your
work, especially if your writing is messy.
Do not stumble around with a longwinded answer that does not solve the problem. If you cannot solve the problem entirely, get as far as you can and write it up nicely. You may get partial credit for keen observations.
Assignment #  Description  Due date 

0  N/A (optional)  
1  Sep 23  
2  Oct 7  
3  Oct 28  
4  Nov 14  
5  Dec 9 
Project Description
In the final project, you will read a paper (or a body of papers) on a topic of your choice that is related to the class. You will present it at a time we will choose at the end of the term. Your presentation will be a typical "conferencestyle" presentation in that you will give a 20 minutes talk using, preferably, slides you prepared. We will pick a 3 hour slot to do this in one shot.
A list of suggested papers can be found here, but feel free to choose any that might interest you.
Marking Breakdown
 (~ 5 marks): Quality of the presentation. Were the slides coherent? Was the flow natural? Were there enough pictures (not needed on every slide, but enough to help the audience visualize what is happening).
 (~ 15 marks): Knowledge of the topic. Were the main results conveyed well? Did you demonstrate a good grasp of the material? Would an attentive audience know the key points and the main ideas behind the proofs? What was the context of the work (i.e. what is it improving over? was it addressing an open problem, or introducing a new problem?). Has there been even more recent work that improved or built on your paper's results? What are directions for future work?
 (~ 5 marks): Were the questions answered well? I may ask questions that probe a bit into the details of some parts, or ones that explore your understanding of the paper in general.
Advice
 Focus more on stating the results cleanly and going over the important ideas leading to the results. Lowlevel details are less important in a 20 minute talk.
 Similarly, do not present every detail of every proof. But still convince me that you understand the work. This is a bit of a balancing act; erring on the side of a cleaner presentation is preferred.
 I want a clear view of the context of the paper(s) you present. What was known before and how did they help advance the state of the art?
 What related problems are left to address?
External Resources
Books
 A large portion of the content is found in Combinatorial Optimization, Theory and Algorithms by Korte and Vygen. UAlberta students have electronic access through our library here.
 An extremely comprehensive reference is Schrijver's book Combinatorial Optimization, Polyhedra and efficiency. The book is in our library (information page).
Other courses with online notes
 Chandra Chekuri's course Topics in Combinatorial Optimization.
 Mohammad R. Salavatipour's course Topics in Algorithms and Combinatorial Optimization.
 Michel Goemans' courses Combinatorial Optimization and Advanced Combinatorial Optimization.
Course Policies
Collaboration Policy
We are adopting the consultation model for colaboration. In particular, it is OK to have verbal discussions about problems with other students but absolutely no written material should be produced or shared in these meetings. You must write up the entire solution yourself.
Late Assignments
I will not accept late submissions. In extreme cases, the weight of an assignment may be transferred to other work required over the term (subject to the instructor's approval).
The final project must be completed, so a student who cannot complete this work on time due to extenuating circumstances can apply for an extension. Deferal of term work is a privilege and not a right; there is no guarantee a deferral will be granted. Misrepresentation of the facts to gain a deferral is a serious breach of the Code of Student Behavior.
Academic Integrity
The University of Alberta is committed to the highest standards of academic integrity and honesty. Students are expected to be familiar with these standards regarding academic honesty and to uphold the policies of the University in this respect. Students are particularly urged to familiarize themselves with the provisions of the Code of Student Behaviour (online at www.governance.ualberta.ca) and avoid any behaviour which could potentially result in suspicions of cheating, plagiarism, misrepresentation of facts and/or participation in an offence. Academic dishonesty is a serious offence and can result in suspension or expulsion from the University.
All forms of dishonesty are unacceptable at the University. Any offence will be reported to the Associate Dean of Science who will determine the disciplinary action to be taken. Cheating, plagiarism and misrepresentation of facts are serious offences. Anyone who engages in these practices will receive at minimum a grade of zero for the exam or paper in question and no opportunity will be given to replace the grade or redistribute the weights. Policy about course outlines can be found in 23.4(2) of the University Calendar.
Disclaimer: Any typographical errors in this Course Outline are subject to change and will be announced in class.