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
- Monte Carlo algorithm for approximate median [note]
- Iterative reweighing with ε-nets: geometric set cover [Mnote]
Apprx shortest paths
- An ADO for weighted undirected graphs [ThoZwi '05]: 7-10
- Spanners for undirected graphs [TS]
- A light apprx shortest path tree [Khuller et al. '95]: 3-9
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
- Highly connected subgraphs [Hoch]: 240-242, 248-262 --- student presentations
LP rounding: deterministic
- Intro to LP [note] --- a review
- Set cover [WS]: 9-14
- A scheduling problem [WS]: 74-78
- Prize-collecting Steiner tree [WS]: 80-83
- Metric uncapacitated facility location [WS]: 83-88
- Bin packing [WS]: 88-93
- Multicut: region growing [WS]: 201-206
- Vertex cover: half-integrality [Vaz]: 121-122
- Generalized assignment [WS]: 280-284
LP rounding: randomized
- Set cover [WS]: 19-22
- Max SAT [WS]: 106-113
- Prize-collecting Steiner tree [WS]: 113-116
- Metric uncapacitated facility location [WS]: 116-119
- Congestion minimization [WS]: 128-129
- Single-source rent-or-buy [WS]: 314-316
Hardness of approximation
- More gap introducing reductions [WS]: 410-414
- Gap preserving reductions parts of [WS]: 414-424

[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