Course Information

Instructor: Zachary Friggstad
Contact Information: click here
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.

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

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

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.

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.

Advice

• 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?

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.