-
Introduction
[WS]: 3-5; [more]
-
Greedy apprx
-
Metric k-center clustering
[WS]: 30-32
-
Set cover
[WS]: 15-17
-
Shortest superstring
[note]
-
Minimizing the maximum lateness
[WS]: 28-30
-
Minimizing the makespan
[WS]: 34-35; [note]
-
Minimum cost Steiner tree
[V]: 27-30
-
Metric TSP
[WS]: 35-40
-
Local search based apprx
-
Minimizing the makespan
[WS]: 32-34
-
Max cut
[KT]: 676-679
-
Maximum independent set of disks
[note]
-
Minimum degree spanning tree
[WS]: 43-46
-
Vizing's edge coloring
[WS]: 47-51
-
Metric uncapacitated facility location
[WS]: 232-238
-
Metric k-median clustering
sketched [WS]: 238-242 --- AR
-
Apprx with dynamic programming
-
Knapsack
[WS]: 57-61
-
Minimizing the makespan
[WS]: 61-66
-
Bin-packing
[WS]: 66-70
-
also refer to Arora's PTAS below
-
Guillotine subdivisions
[Mitch '99]: 2-8
-
Randomized approximation
-
Las Vegas algorithms for max SAT and max cut
[WS]: 100-102, 104-106; [more]
-
Derandomization via conditional expectations: max SAT
[WS]: 103-104
-
Rounding and the power of two choices: max SAT
[WS]: 106-112
-
An ADO for weighted undirected graphs
[ThoZwi '05]: 7-10
-
Monte Carlo algorithm for approximate median
[note]
-
Iterative reweighing: geometric set cover
[Mnote]
-
Apprx using grids
-
Point set diameter
[note]
-
Smallest k-enclosing disk
[PelMaz '05]: 3-5
-
Covering with disks: Hochbaum-Mass shifting
[P]: 151-153
-
Arora's PTAS for the Euclidean TSP
[WS]: 255-267
-
A few more techniques for apprx
-
Isolating cuts: edge multiway cut
[WS]: 194-195
-
Minimum k-cut using Gomory-Hu tree
[V]: 40-44
-
Baker's shifting technique for planar graphs
[wiki]; [note]
-
Tree metrics: uniform buy-at-bulk
[WS]: 210-218
-
Spanners for undirected graphs
[TS]
-
A light apprx shortest path tree
[Khuller et al. '95]: 3-9
-
LP rounding
-
Intro to LP
[note] --- a review
-
Set cover
[WS]: 9-14, 19-22
-
A scheduling problem
[WS]: 74-78
-
Prize-collecting Steiner tree
[WS]: 80-83, 113-116
-
Metric uncapacitated facility location
[WS]: 83-88, 116-119
-
Bin packing
[WS]: 88-93
-
Max SAT
[WS]: 106-113
-
Congestion minimization
[WS]: 128-129
-
Hardness of approximation
-
More gap introducing reductions
[WS]: 410-414
-
Gap preserving reductions
parts of [WS]: 414-424
-
Matchings
-
Maximum weighted bipartite matching
[ScN]: 40-41, 45, 47-50
-
Edmonds maximum cardinality matching
[ScN]: 81-84
-
Minimum weight T-joins
[ChekN]
-
Connectivity
-
All-pairs minimum cuts: Gomory-Hu tree
[ChekN]; [GoemN]: 11-12
-
Karger's algorithm for global minimum cut
[KT]: 714-719
-
Karger-Klein-Tarjan's MST algorithm
[note]
-
Edmonds' minimum cost arborescence
[KT]: 177-183
-
Auslander & Parter's planarity testing algorithm
[Batti]: 74-81
-
Lipton & Trajan's planar separator theorem
[Koz]: 77-83
-
Brooks', 5-colorability, 5-choosability
[W]: 197-198, 257-258, 412
-
[WS]: The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.
-
Additional resources/notes are posted where necessary.
-
AR stands for additional reading (no lecture delivered but included in syllabus).