• Approximation Algorithms
• CS534 at IITG by R. Inkulu

---

• Introduction      [WS]: 3-5; [more]
• Greedy
  • k-Center clustering      [WS]: 30-32
  • Vertex cover      [note]
  • Set cover      [WS]: 16-17
  • Metric TSP      [WS]: 35-40
  • Minimizing the makespan      [WS]: 34-35
• Approx via reductions
  • Shortest superstring to set cover      [Vaz]: 20-22
  • Steiner tree to metric Steiner tree      [Vaz]: 27-29
• Local search
  • Minimizing the makespan      [WS]: 32-34
  • Maximum cut      [KT]: 676-679
  • MIS of axis-par rectangles      [note]
  • Minimum degree spanning tree      [WS]: 43-47
  • Edge coloring: Vizing's      [WS]: 47-51
  • Uncapacitated facility location      [WS]: 232-238
  • k-Median clustering      [WS]: 238-242
• Dynamic programming
  • Knapsack      [WS]: 57-61
  • Minimizing the makespan      [WS]: 61-65
  • Bin-packing      [WS]: 66-70
  • Euclidean TSP: portals      --todo--
  • Guillotine rectangular partition      [note]
• Randomized
  • Max SAT, Max cut      [WS]: 101-102, 104-106
  • Max SAT: derand via cond exp      [WS]: 103-104
  • Max cut: derand via pairwise ind      [MU]: 392-395
  • Single-source rent-or-buy      [WS]: 314-316
  • Unit disk cover: HM's shifting      [note]
  • Geom hitting set: iter reweigh      [note]
• Rounding of SDPs
  • Max cut      [WS]: 137-142
  • Max 2SAT      [note]
  • Correlation clustering      [WS]: 146-149
  • Coloring 3-colorable graphs      [WS]: 149-152
• Rounding of LPs
  • Set cover      [WS]: 9-13, 19-22
  • Weighted sum of completion times      [WS]: 76-80, 119-121
  • Prize-collecting Steiner tree      [WS]: 80-83, 113-115
  • Uncapacitated facility location      [WS]: 83-88, 116-119
  • Max SAT: power of two sols      [WS]: 106-113
  • Congestion minimization      [WS]: 128-129
  • Vertex cover: half-integrality      --todo--
• Primal-dual method
  • Set cover      [WS]: 14-15, 157-159
  • FVS in undirected graphs      [WS]: 160-164
  • Steiner forest      [WS]: 168, 170, 172-174
  • Uncapacitated facility location      [WS]: 177-179, 180
• A few more techniques
  • Set cover: dual fitting      [WS]: 17-18
  • Multiway edge cut: isolating cuts      [WS]: 194-195
  • Minimum k-cut: Gomory-Hu tree      [Vaz]: 40-44
  • k-Center clustering: param pruning      [Vaz]: 47-49, 50-51
  • Maximum independent set: separators      [note]
• Using metrics
  • Multiway edge cut      [WS]: 195-201
  • Multicut: region growing      [WS]: 201-206
  • Sparsest cut   (sans Bourgain's)      [WS]: 370-374
  • Buy-at-bulk: tree metrics      --todo--
• Hardness reductions
  • Gap introducing (two more)      [WS]: 410-412
  • Gap preserving      --todo--



---



• This is an elective course, offered primarily for undergrads. It introduces designing polynomial-time algorithms to compute approximate solutions for classic NP-hard optimization problems. I have offered this course last time during Spring '19.
  
  First, approximations using standard algorithm design techniques are presented, including greedy, divide-and-conquer, local search, dynamic programming, pruning, and random sampling. Then, algorithms based on techniques native to approximations are explored, which include rounding the data, rounding of linear programs, rounding of semidefinite programs, dual fitting, primal-dual method, derandomizing, reductions, grid shifting, iterative reweighing, portals, guillotine cuts, using metrics, region growing, and tree metrics. Furthermore, gap introducing and preserving reductions are introduced to provide worst-case lower bounds on the approximation factors that can be achieved with polynomial-time algorithms.
  
  Problems pursued include the following: set cover, knapsack, bin packing, scheduling, satisfiability; spanning networks, Steiner networks, traveling salesman, cuts in graphs, vertex cover, independent set, feedback vertex set, congestion minimization, colouring; disk cover, partitioning, clustering, facility location.
  
  This course is an extension of CS207; many exciting fundamental ideas that repeatedly occur in algorithm design are emphasized throughout, thereby providing insights into the rich structures underlying various algorithmic problems.
  
  
  
• Texts:
• The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.   [WS]
• [Many additional resources are provided wherever needed.]


• Prereqs: CS101, CS201, CS203, CS205, CS207, and LP.


• Lecture schedule (Slot A1): Mon 3-4:30 pm in 5301; Wed 2:30-4 pm in 5105.
• The academic calendar is here.


• Teaching Assistants: None.


• The grading is relative, and it is based on the total marks obtained in the following:
  
  

  exam1	14 points	10 am to 11:40 am on 30th Jan (Fri) in 5401
  mid-sem	18	2 hours; refer to institute time table
  exam3	15	10 am to 11:40 am on 4th Apr (Sat) in 5401
  presentations	10	by 24th Apr (Fri) 5 pm   [1, 2, 3, 4, 5, 6, 7, 8]
  end-sem	25	3 hours; refer to institute time table
  class participation	4	-

---