# Advanced Algorithms, ETH Zurich, Fall 2020

- Instructor: Mohsen Ghaffari
- Teaching Assistants: Saeed Ilchi, Julian Portmann, and Vaclav Rozhon
- Units: 3V+2U+3A, 9 Credits
- Lecture Time & Place: Wednesdays 09:00-12:00 (online, see the course moodle for zoom link)
- Exercise Session Time & Place: Fridays 10:00-12:00 (online, see the course moodle for zoom link)
- Office Hours: By appointment/email
- Moodle: Advanced Algorithms 2020 on Moodle
- Prerequisite: Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Basic Inequalities.

For instance, having passed the course Algorithms, Probability, and Computing (APC) is highly recommended, though not required formally.

If you're not sure whether you're ready for this class or not, please try Problem Set 00 and consult the instructor. - Other Links: Information on the Course Catalogue of ETH Zurich

Grading: Two graded homeworks 40%, and a 3-hour final exam 60%.

Homeworks, Problem Sets, and Exercise Sessions: During the semester, we will provide some specially-marked graded homeworks. Each of these graded homeworks will account for 20% of your grade.
You should submit your solutions, which __must be typeset in LaTeX__, via moodle. We will send you more detailed instructions via email.
Moreover, we will regularly have other problem sets, roughly one per lecture. You do not need to hand in their solutions.
However, we recommed that you try to solve all of these problems on your own, and seek help from the assistants, if needed. These problem sets will be discussed during the exercise sessions.
The exercise sessions are an indispensable part of the course -- the material covered in them will be included in the final exam and we strongly recommend attending them.

## Lecture Notes:Here are the for this course, but please keep in mind that the lecture notes will be updated throughout the semester. The initial file shows the 2019 edition. The content will be extended and polished, as we go through the semester.
Please see the course moodle for the video recordings of the lectures, and also for the handwritten notes (from the shared screen on the zoom session).
lecture notes |

### Topic List

The following shows the schedule of the course in the 2020 edition. Please see also the 2019 edition. In the 2020 edition, we will follow mostly the same material as the 2019 edition (except at a higher pace) with the addition of a few new topics. The precise schedule and content will be updated throughout the esemester. Hollow bullet points indicate additional sources and optional material.- (16.09) Lecture 01: Approximation Algorithms 1 --- Greedy (Set Cover, Vertex Cover) and Knapsack via Dynamic Programming
- Chapters 1-2, 8-10 in Vazirani's Book on Approximation Algorithms
- Chapters 1-3 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 13 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lectures 1-3 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)

- (23.09) Lecture 02: Approximation Algorithms 2 --- PTAS and FPTAS: Knapsack and Bin Packing, [+ Optional: Minimum Makespan Scheduling]
- Chapters 8-10 in Vazirani's Book on Approximation Algorithms
- Chapter 3 in Williamson & Shmoys's Book on Approximation Algorithms
- Lectures 12-13 of Demaine and Karger (6.854 Advanced Algorithms, MIT, Fall 2003)
- Lecture 3 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)

- (30.09) Lecture 03: Approximation Algorithms 3 --- FPRAS: DNF Counting, [+ Optional: Network Reliability,] and Counting Graph Colorings
- Chapter 28 of Vazirani's Book on Approximation Algorithms
- The 1999 paper of Karger
- Lectures 10 & 11 of Sinclair (CS271 Randomness and Computation, Berkeley, Fall 2011)
- Lectures 14 of Sinclair (CS294 Markov Chain Monte Carlo: Foundations and Applications, Berkeley, Fall 2009)

- (07.10) Lecture 04: Approximation Algorithms 4 --- Rounding Linear Programs: Vertex Cover and Set Cover, Congestion in Multi-Commodity Routing, Matching in Bipartite Graphs, [+ Optional: Scheduling on Unrelated Machines]
- Chapters 14 of Vazirani's Book on Approximation Algorithms
- Chapter 5.11 in Williamson & Shmoys's Book on Approximation Algorithms
- Section 4.3 in Motwani & Raghavan's Book
- Lectures 9 & 10 of Checkuri (CS 583, Approximation Algorithms, UIUC, Spring 2011)

- (15.10) Lecture 05: Approximation Algorithms 5 --- Probabilistic Tree Embedding & Buy-at-Bulk Network Design
- The 1996 paper of Bartal
- The 2003 paper of Fakcharoenphol, Rao, and Talwar
- Sections 8.5 & 8.6 in Williamson & Shmoys's Book on Approximation Algorithms
- Lecture 14 of Gupta (15-859M, Randomized Algorithms, CMU, Spring 2011)
- Lectures 23 of Checkuri (CS 598, Approximation Algorithms, UIUC, Spring 2009)

- (21.10) Lecture 06: Approximation Algorithms 06 --- L1 Metric Embedding & Sparsest Cut
- Is being added as the new Chapter 6 of the Lecture Notes. In the meantime, see moodle for the handwritten notes and video.
- Problem Set 6
- Graded Homework 1. Deadline: 11:59 pm on Nov 6 (submit via Moodle).

- Chapter 21 of Vazirani's Book on Approximation Algorithms
- Lectures 3 of Gupta and Ravi (15-859, Algorithmic Applications of Metric Embeddings, CMU, Fall 2003)
- Lectures 13 of Svensson (Approximation Algorithms and Hardness of Approximation, EPFL, Spring 2013)
- Lectures 19 of Gupta (CS 15-854B, Advanced Approximation Algorithms, CMU Spring 2008)
- Lectures 20 & 21 of Checkuri (CS 598, Approximation Algorithms, UIUC, Spring 2009)
- The 1995 paper of Linial, London, and Rabinovich
- A survey by Indyk on algorithmic applications of embeddings from 2001

### Additional Material:

**Basic Probability Inequalities:**Please make sure that you are comfortable with the basics of probability, e.g., Linearity of Expectation, Markov, Chebyshev, and Chernoff/Hoeffding. You might find the following sources useful: A handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring 2011), and another handout by Angelika Steger and Emo Welzl (Randomized Algorithms and Probabilistic Methods, ETH, Fall 2017).