Spring 2019 — Approximation Algorithms

Location: Soda 373 (there will be some exceptions, check the calendar below)

Time: Every Friday at 6:00pm

Logistics: Please join our mailing list to stay up to date with our meetings and events.

About this Group

Does P = NP? Maybe not, but that should not stop our study of intractable problems. There are several approaches towards dealing with NP-hard discrete optimization problems. One method is to relax optimality requirements, and instead try to find an efficient solution that is “good enough.” The study of approximation algorithms encompasses both designing and analyzing algorithms to quantify what “good enough” means.

This semester, we study various patterns in designing approximation algorithms by surveying a broad sample of intractable problems. We will encounter problems such as Set Cover and Traveling Salesman and more while discussing design patterns such as approximating via local search and primal-dual rounding of linear programs. As a culmination of our studies, we will discuss what it means to be “inapproximable” and how, in certain cases, it is inefficient to derive a reasonable approximation.

Topics Outline

We will be reading through Williamson and Schmoy’s Design of Approximation Algorithms. A copy of this book can be found online here. Refer to this document for a more detailed list of topics.

Introduction to various approximation algorithm design patterns
Greedy and local search algorithms
- Approximating (k)-center
- Christofides algorithm for Traveling Salesman
- Maximizing sub-modular functions
Dynamic programming and the Knapsack problem
Rounding linear programs
- Uncapacitated facility location
- MAX-SAT
Primal-dual algorithms
- Dijkstra’s algorithm as a linear program
- Generalized Steiner Tree
Rounding semidefinite programs
- Approximating MAXCUT
- Coloring 3-Colorable Graphs
Graph cuts: multicut and region growing
Hardness of approximation and the PCP Theorem

Date	Topic	Resources
2/2/2019	Preliminary logistics meeting — Soda 320 @ 5:30pm Discuss plans for weekly meetings and semester long goals.
2/8/2019	Introduction to Approximation Algorithms w/ Set Cover presented by Zod — Soda 373 @ 6:00pm Read WS § 1 A motivation for building approximation algorithms and a tour of design patterns using set cover as an example.	Scribe notes
2/15/2019	A greedy 2-approximation for (k)-center presented by Ida — Soda 373 @ 6:00pm Read WS introduction before § 2.1, § 2.2 Differentiating between greedy and local search algorithms, a 2-approximation for (k)-center, and a proof that this is the optimal approximation ratio unless P=NP.	Scribe notes
2/22/2019	Traveling salesman and Christofides presented by Connor and Nathaniel — Soda 373 @ 6:00pm Read WS § 2.4 introducing traveling salesman and Christofides algorithm.	Scribe notes in progress…
3/1/2019	Maximizing sub-modular functions presented by Antares — Soda 373 @ 6:00pm Read WS § 2.5 about maximizing float in a bank account.	Scribe notes part 1 Scribe notes part 2
3/8/2019	No meeting. * Good luck on midterms!
3/15/2019	Dynamic programming and knapsack presented by Leon and Lily — Soda 373 @ 6:00pm Read WS § 3.1 on applying dynamic programming to construct a FPTAS for dynamic programming.	Scribe notes (draft)
3/22/2019	Rounding linear programs (1) presented by Wilson — Soda 373 @ 6:00pm Read WS § 4.5, § 5.8 on applying LP rounding to uncapacitated facility location.	Scribe notes (draft)
4/5/2019	Rounding linear programs (2) presented by Ayush and Leon — Soda 320 @ 6:00pm Read WS § 5.1, § 5.3 - 5.5 on various LP rounding techniques applied to approximating MAX-SAT.	Scribe notes (draft)
4/12/2019	No meeting. * Good luck on midterms again!
4/19/2019	Primal-dual rounding presented by Robert and Sirej — Soda 373 @ 6:00pm Read WS § 7.3, § 7.4 on primal dual rounding applied to shortest path and generalized steiner tree.	Scribe notes in progress…
4/26/2019	Randomized SDP rounding (1) presented by Zod — Soda 373 @ 6:00pm Read WS § 6.2 on Goemans and Williamson’s algorithm for MAXCUT.	Scribe notes (draft)
5/3/2019	Randomized SDP rounding (2) presented by Lily — Soda 373 @ 6:00pm Read WS § 6.5 on Karger, Motwani and Sudan’s algorithm for 3-Color.	Scribe notes (draft)
5/9/2019	Approx Fest! presented by Antares and Wilson — Cory 212 @ 7:00pm Discuss ball-growing (region growing in WS) and metric LP relaxations along with inapproximability using reductions from unique games. * Read WS § 8.3 on Garg, Vazirani, and Yannakakis’s algorithm for multicut. * Read WS § 16.5 for reductions using the Unique Games Conjecture.	Ball-growing notes Inapproximability notes (draft)