CPSC 531F Tools for Modern Algorithm Analysis 2019 W1
- Instructor:
- Hu Fu
hufu@cs.ubc.ca
ICCS X539, 827-4222
Office Hour: By schedule.
- TA:
- Taylor Lundy
tlundy@cs.ubc.ca
- Piazza:
-
We will be using Piazza for class discussions. Find our class page at:
https://piazza.com/class/jzn8u099q9cje
- Lectures:
- TR 14:00 - 15:30. Location: DMP 101
- Syllabus:
-
This course covers a few topics in algorithm analysis.
Topics we plan to cover include:
- Rounding of linear programs in the design of approximation algorithms
- Randomized rounding of semidefinite programs
- Metric embedding
- Optimal stopping time problems
The first half of the course is driven by techniques. We introduce some key technical ideas and see their applications to different problems. The second half is problem driven. We introduce classes of seemingly similar problems, which are solved via different techniques.
- Texts:
-
There is no single textbook, but many readings will be from the book The Design of Approximation Algorithms by David Shmoys and David Williamson (Cambridge Press, 2011). The book's website provides a free electronic version.
A few readings are assigned from the book Iterative Methods in Combinatorial Optimization by Lpa Chi Lau, R. Ravi and Mohit Singh (Cambridge Press, 2011). An online version of the book is available from UBC library. It is generally a good reference as well for the first part of the course.
Other reading materials will be provided throughout the course.
- Course Work:
-
There will be roughly four problem sets (altogether 40%), a take-home final exam (40%), and a survey project (20%).
- Homework Policies:
-
- will have roughly four problem sets. You are encouraged to work in groups of up to three people for each assignment. Each group needs to turn in only one solution.
- Typesetting solutions using LaTex is highly encouraged. Here is a LaTeX template for your reference.
-
This is a proof-based theory course. Unless stated otherwise, all questions in the problem sets and the exam that ask to design an algorithm, you need to prove your algorithm's correctness. Unless stated otherwise, your algorithm should run in polynomial time.
-
If you do work with someone outside your group or use some outside source, you must acknowledge them in your write-up.
- The survey project:
-
-
You are encouraged to form groups of size (at most) three for the survey project. You are expected to choose a topic from the algorithmic literature in the past 20-30 years, and write a survey on it. The last one or two lectures will be for the class to present the topics they surveyed, and the written survey is due by the end of the semester.
-
The topic you choose should not be too broad, but should comprise at least three papers in its evolution. Your survey should define clearly the problem or the technique that is the object of the survey. It may not provide all proof details, but should describe the general algorithmic approach and key technical innovations made by the major developments.
- The take-home final exam:
-
Each student must complete the final exam independently.
- Schedule:
-
-
Sept 5: Introduction. Review of linear program basics. Integrality of the bipartite matching polytope.
-
Reading: Chapter 2.1 from Lau, Ravi and Singh's book.
-
(Very optional, if you would like to learn more about linear programs) Michel Goemans's notes on linear programs.
- Sept 10: Integrality of the bipartite matching polytope.
-
Reading: Chapter 3.1 from Lau, Ravi and Singh.
- Sept 12: Beck-Fiala Theorem. Steinitz Lemma.
-
Reading:
Miniature 19 and 20 of Jiri Matoušek's book Thirty-three Miniatures.
-
Optional: See Chapter 13.1 from Lau, Ravi and Singh for a presentation of Beck-Fiala theorem in its original context in discrepancy theory. Chapter 13.2 contains a very similar proof of Steinitz Lemma.
- Sept 17: Shmoys and Tardos's result on the Generalized Assignment Problem
- Reading: Chapter 11.1 from Shmoys and Williamson.
- Sept 19, 24, 26: Min-cost bounded degree spanning trees.
-
Reading: Chapter 4 from Lau, Ravi and Singh.
-
Alternatively, read Chapter 11.2 from Shmoys and Williamson.
-
Optional reading: Notes on the ellipsoid algorithm by Michel Goemans.
- Oct 1: Survivable network design.
-
Reading: Chapter 11.3 from Shmoys and Williamson.
- Oct 3: Finishing survivable network design. Introduction to semidefinite programming.
-
Reading: Chapter 6.1 from Shmoys and Williamson.
- Oct 8: Goemans-Williamson approximation algorithm for Max Cut.
-
Reading: Chapter 6.2 from Shmoys and Williamson.
- Oct 10: Shannon capacity and Lovász umbrella.
-
Reading: Miniature 29 of Matoušek's Thirty-three Miniatures;
-
Alternative reading Chapter 42 of Aigner and Ziegler's Proofs from the Book (available online from UBC library). This covers more ground and more details, but the notations may be slightly harder to follow.
-
Optional: Lovász's original paper (On the Shannon Capacity of a Graph), which is exemplarily concise and clean, and covers more properties of the Theta function. We cover the first two sections of the paper.
- Oct 15: Grothendieck inequality and cut norms.
- Reading: Lecture notes by Toniann Pitassi, first three sections.
-
Optional: Khot and Naor's survey on applications of Grothendieck's inequality in combinatorial optimization.
- Oct 17, 22: Sum-of-squares Hierarchy and Pseudo distributions
-
Oct 24: Guest lecture by Nick Harvey on Johnson-Lindenstrauss Theorem
-
Oct 29, 31: Chernoff Bounds.
- Oct 31: Information-theoretic lower bounds for distinguishing biased coins
-
Reading: Lecture notes (section 1.1 and 1.2) by Bobby Kleinberg on Information-theoretic lower bounds for distinguishing biased coins.
- Nov 5, 7: Bourgain's metric embedding theorem.
-
Reading: Chapter 15.1 from Shmoys and Williamson.
- Nov 12: Applications of Bourgain's theorem.
- Nov 14: FRT tree metric embedding.
- Reading: Chapter 8.5 from Shmoys and Williamson.
- Nov 19: Finishing FRT. The secretary problem.
- Nov 21: Lower bound of secretary problem. Single item prophet inequality. Pandora Box problem.
- Nov 26: Gittins Index Algorithm.
- Nov 28: Class presentation of projects (surveys on algorithmic topics).