# Approximation Algorithm

- Institution: IIT Kharagpur
- Department: Computer Science and Engineering
- Teacher: Prof. Palash Dey
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106105471)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106105471)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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.

Intended audience: Under-graduate and post-graduate students and faculty members.

Prerequisites: Knowledge of algorithm design principles.

## Lectures

1. [Lecture 01 : Overview of NP-completeness and How to Tackle It](https://invisiblenetwork.ai/learn/nptel/106105471/6baf9e3957c9) (YouTube)
2. [Lecture 02 : Deterministic Rounding of Linear Program: An Approximation Algorithm for Weighted Set Cover](https://invisiblenetwork.ai/learn/nptel/106105471/9f64e611da1f) (YouTube)
3. [Lecture 03 : Overview of LP Duality and Complementary Slackness](https://invisiblenetwork.ai/learn/nptel/106105471/daa570067d3d) (YouTube)
4. [Lecture 04 : Dual Rounding: An Approximation Algorithm for Weighted Set Cover](https://invisiblenetwork.ai/learn/nptel/106105471/180e60e08246) (YouTube)
5. [Lecture 05 : Primal dual method for Weighted Set Cover](https://invisiblenetwork.ai/learn/nptel/106105471/52632b1b60eb) (YouTube)
6. [Lecture 06 : Greedy algorithm for Weighted Set Cover](https://invisiblenetwork.ai/learn/nptel/106105471/c292ac2adea1) (YouTube)
7. [Lecture 07 : Dual Fitting Analysis of Greedy Set Cover](https://invisiblenetwork.ai/learn/nptel/106105471/f12a93862740) (YouTube)
8. [Lecture 08 : Randomized Rounding Algorithm for Weighted Set Cover](https://invisiblenetwork.ai/learn/nptel/106105471/8aba1fa71628) (YouTube)
9. [Lecture 09 : Scheduling Jobs with Deadlines and Release Dates on a Single Machine](https://invisiblenetwork.ai/learn/nptel/106105471/610dd16702f5) (YouTube)
10. [Lecture 10 : The k-Center Problem](https://invisiblenetwork.ai/learn/nptel/106105471/d0f0f3624f1d) (YouTube)
11. [Lecture 11 : Local Search Algorithm for Scheduling Jobs on Multiple Identical Machines](https://invisiblenetwork.ai/learn/nptel/106105471/fba1b01037e7) (YouTube)
12. [Lecture 12 : Greedy Algorithm for Scheduling Jobs on Multiple Identical Machines](https://invisiblenetwork.ai/learn/nptel/106105471/e792ee9c13ed) (YouTube)
13. [Lecture 13 : Inapproximability of the Traveling Salesman problem](https://invisiblenetwork.ai/learn/nptel/106105471/4c3ed66e4fa9) (YouTube)
14. [Lecture 14 : 2-Approximation Algorithm for Metric TSP](https://invisiblenetwork.ai/learn/nptel/106105471/92367b664e0e) (YouTube)
15. [Lecture 15 : 1.5-Approximation Algorithm for Metric TSP](https://invisiblenetwork.ai/learn/nptel/106105471/6d89cd2a4759) (YouTube)
16. [Lecture 16 : Edge Coloring](https://invisiblenetwork.ai/learn/nptel/106105471/dcec3a1da7f7) (YouTube)
17. [Lecture 17 : Pseudo Polynomial Time Algorithm for Knapsack](https://invisiblenetwork.ai/learn/nptel/106105471/c77db670c60a) (YouTube)
18. [Lecture 18 : FPTAS for Knapsack](https://invisiblenetwork.ai/learn/nptel/106105471/9d90d12cb4ca) (YouTube)
19. [Lecture 19 : PTAS for Minimizing Makespan for Scheduling Jobs on Constant Number of Machines](https://invisiblenetwork.ai/learn/nptel/106105471/e93835e044f7) (YouTube)
20. [Lecture 20 : PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines](https://invisiblenetwork.ai/learn/nptel/106105471/78cb50f9849c) (YouTube)
21. [Lecture 21 : PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/237885763fe6) (YouTube)
22. [Lecture 22 : An APTAS for Bin Packing](https://invisiblenetwork.ai/learn/nptel/106105471/40afcd3bb264) (YouTube)
23. [Lecture 23 : An APTAS for Bin Packing Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/3c94e83ee70b) (YouTube)
24. [Lecture 24 : 2 Factor Approximation Algorithm for Scheduling Unweighted Jobs on a Single Machine](https://invisiblenetwork.ai/learn/nptel/106105471/63b5ab5ed883) (YouTube)
25. [Lecture 25 : 3 Factor Approximation Algorithm for Scheduling Weighted Jobs on a Single Machine](https://invisiblenetwork.ai/learn/nptel/106105471/702c88b455fc) (YouTube)
26. [Lecture 26 : A Polynomial Time Separation Oracle for Scheduling Weighted Jobs on a Single Machine](https://invisiblenetwork.ai/learn/nptel/106105471/32838c0a1edd) (YouTube)
27. [Lecture 27 : 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree](https://invisiblenetwork.ai/learn/nptel/106105471/6fe55bbf4b7d) (YouTube)
28. [Lecture 28 : 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/10577cecfd56) (YouTube)
29. [Lecture 29 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem](https://invisiblenetwork.ai/learn/nptel/106105471/ac95b025cf61) (YouTube)
30. [Lecture 30 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/4170c28959db) (YouTube)
31. [Lecture 31 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/bd546b4b64f2) (YouTube)
32. [Lecture 32 : Randomized 1/2 Factor Approximation Algorithm for MAX-SAT and MAX-CUT](https://invisiblenetwork.ai/learn/nptel/106105471/3ef2662b41e6) (YouTube)
33. [Lecture 33 : Derandomization using Method of Conditional Expectation](https://invisiblenetwork.ai/learn/nptel/106105471/c9050640d0a8) (YouTube)
34. [Lecture 34 : Flipping Biased Coin for Better Than .5 Approximation Algorithm for Max-SAT](https://invisiblenetwork.ai/learn/nptel/106105471/61e8f0682f6a) (YouTube)
35. [Lecture 35 : Randomized Rounding Based (1-1/e) Factor Approximation Algorithm for Max-SAT](https://invisiblenetwork.ai/learn/nptel/106105471/849b7ffe5652) (YouTube)
36. [Lecture 36 : Best of Two Solutions for Max-SAT](https://invisiblenetwork.ai/learn/nptel/106105471/950669a1a42f) (YouTube)
37. [Lecture 37 : Nonlinear Rounding for Max-SAT](https://invisiblenetwork.ai/learn/nptel/106105471/a9e489261faa) (YouTube)
38. [Lecture 38 : Randomized Rounding for Prize Collecting Steiner Tree](https://invisiblenetwork.ai/learn/nptel/106105471/017d373f51cd) (YouTube)
39. [Lecture 39 : Randomized Rounding for Prize Collecting Steiner Tree Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/469c4fec6ded) (YouTube)
40. [Lecture 40 : Randomized Rounding for Uncapacitated Facility Location](https://invisiblenetwork.ai/learn/nptel/106105471/e801820a75e6) (YouTube)
41. [Lecture 41 : Chernoff Bound](https://invisiblenetwork.ai/learn/nptel/106105471/500ca0450db8) (YouTube)
42. [Lecture 42 : Chernoff Bound Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/3f56dfdf5e91) (YouTube)
43. [Lecture 43 : Integer Multicommodity Flow](https://invisiblenetwork.ai/learn/nptel/106105471/699f8a06bb5c) (YouTube)
44. [Lecture 44 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set](https://invisiblenetwork.ai/learn/nptel/106105471/67b4c1580593) (YouTube)
45. [Lecture 45 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/23d91a47324a) (YouTube)
46. [Lecture 46 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/60673044348b) (YouTube)
47. [Lecture 47 : Primal-dual Algorithm for Steiner Forest](https://invisiblenetwork.ai/learn/nptel/106105471/61fdc34cd8a7) (YouTube)
48. [Lecture 48 : Primal-dual Algorithm for Steiner Forest Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/ecd7bf979264) (YouTube)
49. [Lecture 49 : Primal-dual Algorithm for Steiner Forest Contd.](https://invisiblenetwork.ai/learn/nptel/106105471/3225b8d0729d) (YouTube)
50. [Lecture 50 : 2- Approximation Algorithm for Multiway Cut](https://invisiblenetwork.ai/learn/nptel/106105471/15d97c98375b) (YouTube)
51. [Lecture 51 : 3/2-Approximation Algorithm for Multiway Cut](https://invisiblenetwork.ai/learn/nptel/106105471/b9a6d2bef3a9) (YouTube)
52. [Lecture 52 : 3/2-Approximation Algorithm for Multiway Cut Cont.](https://invisiblenetwork.ai/learn/nptel/106105471/2920c53ed8c1) (YouTube)
53. [Lecture 53 : Approximation Algorithm for Multicut](https://invisiblenetwork.ai/learn/nptel/106105471/1a414969ac85) (YouTube)
54. [Lecture 54 : Approximation Algorithm for Multicut Cont.](https://invisiblenetwork.ai/learn/nptel/106105471/987c77967733) (YouTube)
55. [Lecture 55 : Approximation Algorithm for Multicut Cont.](https://invisiblenetwork.ai/learn/nptel/106105471/64b1127bda3f) (YouTube)
56. [Lecture 56 : Introduction to Semidefinite Program](https://invisiblenetwork.ai/learn/nptel/106105471/2fedfc645ec1) (YouTube)
57. [Lecture 57 : SDP Based Approximation Algorithm for Max Cut](https://invisiblenetwork.ai/learn/nptel/106105471/089857945e53) (YouTube)
58. [Lecture 58 : SDP Based Approximation Algorithm for Max Cut Cont](https://invisiblenetwork.ai/learn/nptel/106105471/3c1fb490969f) (YouTube)
59. [Lecture 59 : Inapproximability of Scheduling Jobs on Multiple Non-identical Machines](https://invisiblenetwork.ai/learn/nptel/106105471/7cd42389a36e) (YouTube)
60. [Lecture 60 : Inapproximability of Edge Disjoint Path](https://invisiblenetwork.ai/learn/nptel/106105471/c18bbc219804) (YouTube)