# Course Information

Lecture: MWF 1:00-1:50pm in CSC B-41
Office Hours: Tuesday 1:00-1:50pm, Wednesday 2:00 - 2:50 in ATH 3-06

## Outline

One of the main goals 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.

### 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); minimum-weight perfect matchings; certificates of optimality.
• Flows and Cuts
Single commodity flows; max-flow/min-cut theorem; circulations; Hoffman's circulation theorem; minimum-cost flows; Gomery-Hu 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 NP-hard 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 NP-hard 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 min-weight or max-value 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 polynomial-time algorithms to solve problems exactly, we will see a few approximation algorithms along the way (algorithms that find provably near-optimum solutions to NP-hard 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.
• Edge-Based 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 $s-t$ 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 PSPACE-complete 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 NP-hard problems.
• Multicommodity flow/cut gap and Klein-Plotkin-Rao decompositions.
• The Okamura-Seymour 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.
• Lift-and-Project Techniques
A recently-popular method for strengthening convex relaxations of discrete optimization problems is the lift-and-project 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 Sherali-Adams or Sum-of-Squares technique.

### 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 self-contained 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 9-21) to give the presentations.

A ≥ 80% > B ≥ 70% > C ≥ 60% > D ≥ 50% > F

# Lecture Notes

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, Max-Flow/Min-Cut Bradley Hauer KV 8.1
Interesting note: exercise 2 in Chapter 8 of KV shows that the Ford-Fulkerson algorithm may never terminate if capacities are irrational.
3 Efficient Flows Chris Martin KV 8.3
4 Push-Relabel Analysis Zac Friggstad KV 8.5
5 Undirected Cuts and Gomery-Hu Trees Zac Friggstad KV 8.6
6 Gomery-Hu Trees cont. Mirmahdi Rahgoshay KV 8.6
7 Graph Potentials and Minimum-Cost 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 minimum-cost transshipment (using our terminology). But the two are easily seen to be equivalent views (based on the connection between max flow and transshipments/b-flows).
8 Minimum-Cost 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 minimum-ratio cycles in $O(nm)$ time. It uses the table of distances calculated by the Bellman-Ford 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's-Gallai 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 min-cost 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).
21-23 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 low-level 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
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 .pdf N/A (optional)
1 .pdf Sep 23
2 .pdf Oct 7
3 .pdf Oct 28
4 .pdf Nov 14
5 .pdf 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 "conference-style" 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.

• Focus more on stating the results cleanly and going over the important ideas leading to the results. Low-level 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?

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