• Approximation Algorithms
• CS534 at IITG by R. Inkulu

---

• Introduction      [WS]: 3-5; [more]
• Greedy
  • Metric k-center clustering      [WS]: 30-31
  • Vertex cover      [note]
  • Set cover      [WS]: 16-


-- as the course progress, topics covered in lectures are listed here ---




---



• This is an elective course, offered to both undergrad and grad students. It introduces designing polynomial-time algorithms to compute approximate solutions for optimization problems.
  
  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 linear programs, primal-dual method, region growing, grid shifting, tree metrics, coresets, and epsilon-nets. Furthermore, 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, assignment, satisfiability; spanning networks, Steiner networks, spanner networks, traveling salesman, subgraph search, cuts in graphs, congestion minimization, colouring; disk cover, 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, CS207.


• Lectures are held in 5401 in Slot A1: Mon 5-5:55 pm, Tue 4-4:55 pm, Th 2-2:55 pm.
• 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 (Sat) 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
  presentation	10	mutual convenience
  end-sem	25	3 hours; refer to institute time table
  class participation	4	-

---