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.

Files: scribe note template

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)