IIT Kharagpur · Computer Science

Approximation Algorithm

Prof. Palash Dey · 2025 · 60 free video lectures

Many real-world problems are NP-complete. Hence, they are unlikely to admit a polynomial-time algorithm. In this course, we will study various techniques to design efficient algorithms to compute an approximately optimal solutions.

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 01 : Overview of NP-completeness and How to Tackle It
  2. Lecture 02 : Deterministic Rounding of Linear Program: An Approximation Algorithm for Weighted Set Cover
  3. Lecture 03 : Overview of LP Duality and Complementary Slackness
  4. Lecture 04 : Dual Rounding: An Approximation Algorithm for Weighted Set Cover
  5. Lecture 05 : Primal dual method for Weighted Set Cover
  6. Lecture 06 : Greedy algorithm for Weighted Set Cover
  7. Lecture 07 : Dual Fitting Analysis of Greedy Set Cover
  8. Lecture 08 : Randomized Rounding Algorithm for Weighted Set Cover
  9. Lecture 09 : Scheduling Jobs with Deadlines and Release Dates on a Single Machine
  10. Lecture 10 : The k-Center Problem
  11. Lecture 11 : Local Search Algorithm for Scheduling Jobs on Multiple Identical Machines
  12. Lecture 12 : Greedy Algorithm for Scheduling Jobs on Multiple Identical Machines
  13. Lecture 13 : Inapproximability of the Traveling Salesman problem
  14. Lecture 14 : 2-Approximation Algorithm for Metric TSP
  15. Lecture 15 : 1.5-Approximation Algorithm for Metric TSP
  16. Lecture 16 : Edge Coloring
  17. Lecture 17 : Pseudo Polynomial Time Algorithm for Knapsack
  18. Lecture 18 : FPTAS for Knapsack
  19. Lecture 19 : PTAS for Minimizing Makespan for Scheduling Jobs on Constant Number of Machines
  20. Lecture 20 : PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines
  21. Lecture 21 : PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines Contd.
  22. Lecture 22 : An APTAS for Bin Packing
  23. Lecture 23 : An APTAS for Bin Packing Contd.
  24. Lecture 24 : 2 Factor Approximation Algorithm for Scheduling Unweighted Jobs on a Single Machine
  25. Lecture 25 : 3 Factor Approximation Algorithm for Scheduling Weighted Jobs on a Single Machine
  26. Lecture 26 : A Polynomial Time Separation Oracle for Scheduling Weighted Jobs on a Single Machine
  27. Lecture 27 : 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree
  28. Lecture 28 : 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree Contd.
  29. Lecture 29 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem
  30. Lecture 30 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd.
  31. Lecture 31 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd.
  32. Lecture 32 : Randomized 1/2 Factor Approximation Algorithm for MAX-SAT and MAX-CUT
  33. Lecture 33 : Derandomization using Method of Conditional Expectation
  34. Lecture 34 : Flipping Biased Coin for Better Than .5 Approximation Algorithm for Max-SAT
  35. Lecture 35 : Randomized Rounding Based (1-1/e) Factor Approximation Algorithm for Max-SAT
  36. Lecture 36 : Best of Two Solutions for Max-SAT
  37. Lecture 37 : Nonlinear Rounding for Max-SAT
  38. Lecture 38 : Randomized Rounding for Prize Collecting Steiner Tree
  39. Lecture 39 : Randomized Rounding for Prize Collecting Steiner Tree Contd.
  40. Lecture 40 : Randomized Rounding for Uncapacitated Facility Location
  41. Lecture 41 : Chernoff Bound
  42. Lecture 42 : Chernoff Bound Contd.
  43. Lecture 43 : Integer Multicommodity Flow
  44. Lecture 44 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set
  45. Lecture 45 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set Contd.
  46. Lecture 46 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set Contd.
  47. Lecture 47 : Primal-dual Algorithm for Steiner Forest
  48. Lecture 48 : Primal-dual Algorithm for Steiner Forest Contd.
  49. Lecture 49 : Primal-dual Algorithm for Steiner Forest Contd.
  50. Lecture 50 : 2- Approximation Algorithm for Multiway Cut
  51. Lecture 51 : 3/2-Approximation Algorithm for Multiway Cut
  52. Lecture 52 : 3/2-Approximation Algorithm for Multiway Cut Cont.
  53. Lecture 53 : Approximation Algorithm for Multicut
  54. Lecture 54 : Approximation Algorithm for Multicut Cont.
  55. Lecture 55 : Approximation Algorithm for Multicut Cont.
  56. Lecture 56 : Introduction to Semidefinite Program
  57. Lecture 57 : SDP Based Approximation Algorithm for Max Cut
  58. Lecture 58 : SDP Based Approximation Algorithm for Max Cut Cont
  59. Lecture 59 : Inapproximability of Scheduling Jobs on Multiple Non-identical Machines
  60. Lecture 60 : Inapproximability of Edge Disjoint Path

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kharagpur.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights