NOC:Approximation Algorithm

Lecture 1 - Overview of NP-completeness and How to Tackle It

Lecture 2 - Deterministic Rounding of Linear Program: An Approximation Algorithm for Weighted

Lecture 3 - Overview of LP Duality and Complementary Slackness

Lecture 4 - Dual Rounding: An Approximation Algorithm for Weighted Set Cover

Lecture 5 - Primal dual method for Weighted Set Cover

Lecture 6 - Greedy algorithm for Weighted Set Cover

Lecture 7 - Dual Fitting Analysis of Greedy Set Cover

Lecture 8 - Randomized Rounding Algorithm for Weighted Set Cover

Lecture 9 - Scheduling Jobs with Deadlines and Release Dates on a Single Machine

Lecture 10 - The k-Center Problem

Lecture 11 - Local Search Algorithm for Scheduling Jobs on Multiple Identical Machines

Lecture 12 - Greedy Algorithm for Scheduling Jobs on Multiple Identical Machines

Lecture 13 - Inapproximability of the Traveling Salesman problem

Lecture 14 - 2-Approximation Algorithm for Metric TSP

Lecture 15 - 1.5-Approximation Algorithm for Metric TSP

Lecture 16 - Edge Coloring

Lecture 17 - Pseudo Polynomial Time Algorithm for Knapsack

Lecture 18 - FPTAS for Knapsack

Lecture 19 - PTAS for Minimizing Makespan for Scheduling Jobs on Constant Number of Machines

Lecture 20 - PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines

Lecture 21 - PTAS for Minimizing Makespan for Scheduling Jobs on Parallel Identical Machines (Continued...)

Lecture 22 - An APTAS for Bin Packing

Lecture 23 - An APTAS for Bin Packing (Continued...)

Lecture 24 - 2 Factor Approximation Algorithm for Scheduling Unweighted Jobs on a Single Machine

Lecture 25 - 3 Factor Approximation Algorithm for Scheduling Weighted Jobs on a Single Machine

Lecture 26 - A Polynomial Time Separation Oracle for Scheduling Weighted Jobs on a Single Machine

Lecture 27 - 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree

Lecture 28 - 3 Factor Approximation Algorithm for Prize Collecting Steiner Tree (Continued...)

Lecture 29 - A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem

Lecture 30 - A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem (Continued...)

Lecture 31 - A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem (Continued...)

Lecture 32 - Randomized 1/2 Factor Approximation Algorithm for MAX-SAT and MAX-CUT

Lecture 33 - Derandomization using Method of Conditional Expectation

Lecture 34 - Flipping Biased Coin for Better Than .5 Approximation Algorithm for Max-SAT

Lecture 35 - Randomized Rounding Based (1-1/e) Factor Approximation Algorithm for Max-SAT

Lecture 36 - Best of Two Solutions for Max-SAT

Lecture 37 - Nonlinear Rounding for Max-SAT

Lecture 38 - Randomized Rounding for Prize Collecting Steiner Tree

Lecture 39 - Randomized Rounding for Prize Collecting Steiner Tree (Continued...)

Lecture 40 - Randomized Rounding for Uncapacitated Facility Location

Lecture 41 - Chernoff Bound

Lecture 42 - Chernoff Bound (Continued...)

Lecture 43 - Integer Multicommodity Flow

Lecture 44 - Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set

Lecture 45 - Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set (Continued...)

Lecture 46 - Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set (Continued...)

Lecture 47 - Primal-dual Algorithm for Steiner Forest

Lecture 48 - Primal-dual Algorithm for Steiner Forest (Continued...)

Lecture 49 - Primal-dual Algorithm for Steiner Forest (Continued...)

Lecture 50 - 2-Approximation Algorithm for Multiway Cut

Lecture 51 - 3/2-Approximation Algorithm for Multiway Cut

Lecture 52 - 3/2-Approximation Algorithm for Multiway Cut (Continued...)

Lecture 53 - Approximation Algorithm for Multicut

Lecture 54 - Approximation Algorithm for Multicut (Continued...)

Lecture 55 - Approximation Algorithm for Multicut (Continued...)

Lecture 56 - Introduction to Semidefinite Program

Lecture 57 - SDP Based Approximation Algorithm for Max Cut

Lecture 58 - SDP Based Approximation Algorithm for Max Cut (Continued...)

Lecture 59 - Inapproximability of Scheduling Jobs on Multiple Non-identical Machines

Lecture 60 - Inapproximability of Edge Disjoint Path