Advanced Algorithms

Advanced Algorithms
CS520 at IITG by R. Inkulu

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 [Vaz]: 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 using grids
- Point set diameter [note]
- Smallest k-enclosing disk [PelMaz '05]: 3-5
- Covering with disks: Hochbaum-Mass shifting [P]: 151-153
Apprx with dynamic programming
- Knapsack [WS]: 57-61
- Minimizing the makespan [WS]: 61-66
- Bin-packing [WS]: 66-70
- Arora's PTAS for Euclidean TSP [WS]: 255-267
- Mitchell's guillotine cuts [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]
A few more techniques for apprx
- Isolating cuts: edge multiway cut [WS]: 194-195
- Minimum k-cut using Gomory-Hu tree [Vaz]: 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
- Multicut: region growing [WS]: 201-206 --- not covered this time
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]
- Brooks' theorem for vertex coloring [W]: 197-198
- 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

[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).

Guidelines Spring '17