Learn · NPTEL

Course10610547160 lectures

Approximation Algorithm

Prof. Palash Dey · IIT Kharagpur

Start with lecture 1 At NPTEL

About

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

Week 1:

  1. Lecture 01 : Overview of NP-completeness and How to Tackle It YouTube
  2. Lecture 02 : Deterministic Rounding of Linear Program: An Approximation Algorithm for Weighted Set Cover YouTube
  3. Lecture 03 : Overview of LP Duality and Complementary Slackness YouTube
  4. Lecture 04 : Dual Rounding: An Approximation Algorithm for Weighted Set Cover YouTube
  5. Lecture 05 : Primal dual method for Weighted Set Cover YouTube

Week 2:

  1. Lecture 06 : Greedy algorithm for Weighted Set Cover YouTube
  2. Lecture 07 : Dual Fitting Analysis of Greedy Set Cover YouTube
  3. Lecture 08 : Randomized Rounding Algorithm for Weighted Set Cover YouTube
  4. Lecture 09 : Scheduling Jobs with Deadlines and Release Dates on a Single Machine YouTube
  5. Lecture 10 : The k-Center Problem YouTube

Week 3 :

  1. Lecture 11 : Local Search Algorithm for Scheduling Jobs on Multiple Identical Machines YouTube
  2. Lecture 12 : Greedy Algorithm for Scheduling Jobs on Multiple Identical Machines YouTube
  3. Lecture 13 : Inapproximability of the Traveling Salesman problem YouTube
  4. Lecture 14 : 2-Approximation Algorithm for Metric TSP YouTube
  5. Lecture 15 : 1.5-Approximation Algorithm for Metric TSP YouTube

Week 4 :

  1. Lecture 16 : Edge Coloring YouTube
  2. Lecture 17 : Pseudo Polynomial Time Algorithm for Knapsack YouTube
  3. Lecture 18 : FPTAS for Knapsack YouTube
  4. Lecture 19 : PTAS for Minimizing Makespan for Scheduling Jobs on Constant Number of Machines YouTube
  5. Lecture 20 : PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines YouTube

Week 5 :

  1. Lecture 21 : PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines Contd. YouTube
  2. Lecture 22 : An APTAS for Bin Packing YouTube
  3. Lecture 23 : An APTAS for Bin Packing Contd. YouTube
  4. Lecture 24 : 2 Factor Approximation Algorithm for Scheduling Unweighted Jobs on a Single Machine YouTube
  5. Lecture 25 : 3 Factor Approximation Algorithm for Scheduling Weighted Jobs on a Single Machine YouTube

Week 6 :

  1. Lecture 26 : A Polynomial Time Separation Oracle for Scheduling Weighted Jobs on a Single Machine YouTube
  2. Lecture 27 : 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree YouTube
  3. Lecture 28 : 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree Contd. YouTube
  4. Lecture 29 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem YouTube
  5. Lecture 30 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd. YouTube

Week 7 :

  1. Lecture 31 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd. YouTube
  2. Lecture 32 : Randomized 1/2 Factor Approximation Algorithm for MAX-SAT and MAX-CUT YouTube
  3. Lecture 33 : Derandomization using Method of Conditional Expectation YouTube
  4. Lecture 34 : Flipping Biased Coin for Better Than .5 Approximation Algorithm for Max-SAT YouTube
  5. Lecture 35 : Randomized Rounding Based (1-1/e) Factor Approximation Algorithm for Max-SAT YouTube

Week 8 :

  1. Lecture 36 : Best of Two Solutions for Max-SAT YouTube
  2. Lecture 37 : Nonlinear Rounding for Max-SAT YouTube
  3. Lecture 38 : Randomized Rounding for Prize Collecting Steiner Tree YouTube
  4. Lecture 39 : Randomized Rounding for Prize Collecting Steiner Tree Contd. YouTube
  5. Lecture 40 : Randomized Rounding for Uncapacitated Facility Location YouTube

Week 9 :

  1. Lecture 41 : Chernoff Bound YouTube
  2. Lecture 42 : Chernoff Bound Contd. YouTube
  3. Lecture 43 : Integer Multicommodity Flow YouTube
  4. Lecture 44 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set YouTube
  5. Lecture 45 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set Contd. YouTube

Week 10 :

  1. Lecture 46 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set Contd. YouTube
  2. Lecture 47 : Primal-dual Algorithm for Steiner Forest YouTube
  3. Lecture 48 : Primal-dual Algorithm for Steiner Forest Contd. YouTube
  4. Lecture 49 : Primal-dual Algorithm for Steiner Forest Contd. YouTube
  5. Lecture 50 : 2- Approximation Algorithm for Multiway Cut YouTube

Week 11 :

  1. Lecture 51 : 3/2-Approximation Algorithm for Multiway Cut YouTube
  2. Lecture 52 : 3/2-Approximation Algorithm for Multiway Cut Cont. YouTube
  3. Lecture 53 : Approximation Algorithm for Multicut YouTube
  4. Lecture 54 : Approximation Algorithm for Multicut Cont. YouTube
  5. Lecture 55 : Approximation Algorithm for Multicut Cont. YouTube

Week 12 :

  1. Lecture 56 : Introduction to Semidefinite Program YouTube
  2. Lecture 57 : SDP Based Approximation Algorithm for Max Cut YouTube
  3. Lecture 58 : SDP Based Approximation Algorithm for Max Cut Cont YouTube
  4. Lecture 59 : Inapproximability of Scheduling Jobs on Multiple Non-identical Machines YouTube
  5. Lecture 60 : Inapproximability of Edge Disjoint Path YouTube

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kharagpur
Department
Computer Science and Engineering
Teacher
Prof. Palash Dey
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed