Learn · Approximation Algorithm
Lecture 24 of 60Week 5 :
Lecture 24 : 2 Factor Approximation Algorithm for Scheduling Unweighted Jobs on a Single Machine
Prof. Palash Dey · IIT Kharagpur
Credits and licence
- From
- Approximation Algorithm, IIT Kharagpur (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Lecture 01 : Overview of NP-completeness and How to Tackle It
- Lecture 02 : Deterministic Rounding of Linear Program: An Approximation Algorithm for Weighted Set Cover
- Lecture 03 : Overview of LP Duality and Complementary Slackness
- Lecture 04 : Dual Rounding: An Approximation Algorithm for Weighted Set Cover
- Lecture 05 : Primal dual method for Weighted Set Cover
- Lecture 06 : Greedy algorithm for Weighted Set Cover
- Lecture 07 : Dual Fitting Analysis of Greedy Set Cover
- Lecture 08 : Randomized Rounding Algorithm for Weighted Set Cover
- Lecture 09 : 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 Contd.
- Lecture 22 : An APTAS for Bin Packing
- Lecture 23 : An APTAS for Bin Packing Contd.
- 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 Contd.
- Lecture 29 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem
- Lecture 30 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd.
- Lecture 31 : A 4 Factor Approximation Algorithm for Uncapacitated Facility Location Problem Contd.
- 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 Contd.
- Lecture 40 : Randomized Rounding for Uncapacitated Facility Location
- Lecture 41 : Chernoff Bound
- Lecture 42 : Chernoff Bound Contd.
- 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 Contd.
- Lecture 46 : Primal-dual Algorithm for Minimum Weighted Feedback Vertex Set Contd.
- Lecture 47 : Primal-dual Algorithm for Steiner Forest
- Lecture 48 : Primal-dual Algorithm for Steiner Forest Contd.
- Lecture 49 : Primal-dual Algorithm for Steiner Forest Contd.
- 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 Cont.
- Lecture 53 : Approximation Algorithm for Multicut
- Lecture 54 : Approximation Algorithm for Multicut Cont.
- Lecture 55 : Approximation Algorithm for Multicut Cont.
- Lecture 56 : Introduction to Semidefinite Program
- Lecture 57 : SDP Based Approximation Algorithm for Max Cut
- Lecture 58 : SDP Based Approximation Algorithm for Max Cut Cont
- Lecture 59 : Inapproximability of Scheduling Jobs on Multiple Non-identical Machines
- Lecture 60 : Inapproximability of Edge Disjoint Path