Vertex cover and Linear Programming-Introduction: a roadmap to this module and to this course
Lecture: Introduction
()
Slides
All slides for all chapters of Approx Algs part 1
Attempt to upload slides in Keynote format
Vertex cover and Linear Programming-What is vertex cover? Some examples
Lecture: Definition
()
Slides
Vertex cover and Linear Programming-An integer program for vertex cover
Lecture: Integer program
()
Slides
Vertex cover and Linear Programming-Integer programming and linear programming
Lecture: A linear programming relaxation
()
Slides
Vertex cover and Linear Programming-An approximation algorithm for vertex cover
Lecture: Approximation algorithm
()
Slides
Vertex cover and Linear Programming-Analysis: how good is our algorithm ?
Lecture: Analysis
()
Slides
Vertex cover and Linear Programming-General facts
Lecture: General facts
()
Slides
Vertex cover and Linear Programming-Exercises
Practice Exercises
PDF version of the peer-graded assignment
Half integrality (7:35 bug, fixed in pdf slides)
()
Half-integrality slides
All slides together in one file
Knapsack and Rounding-The knapsack problem: Definition
Lecture: Definition
()
Slides
Knapsack and Rounding-Greedy algorithm
Lecture: Greedy algorithm
()
Slides
Knapsack and Rounding-Dynamic programming in special case
Lecture: Special dynamic program
()
Slides
Knapsack and Rounding-Dynamic programming in general
Lecture: General dynamic program
()
Slides
Knapsack and Rounding-Approximation algorithm
Lecture: algorithm
()
Slides
Knapsack and Rounding-Analysis
Lecture: analysis
()
Slides
Knapsack and Rounding-Approximation scheme
Lecture: approximation scheme
()
Slides
Knapsack and Rounding-Exercises
Practise Exercises
All slides together in one file
Bin Packing, Linear Programming and Rounding-The Next-Fit algorithm
Lecture: Next Fit
()
Slides (with typo corrected)
Bin Packing, Linear Programming and Rounding-A linear program for Bin-Packing
Lecture: a linear program
()
Slides
Bin Packing, Linear Programming and Rounding-Small items
Lecture: small items
()
Slides
Bin Packing, Linear Programming and Rounding-Large items, few sizes
Lecture: large items, few sizes
()
Slides
Bin Packing, Linear Programming and Rounding-Large items, many sizes
Slides
Large items, many sizes
()
Bin Packing, Linear Programming and Rounding-Large items, analysis
Lecture: large items analysis
()
Slides
Bin Packing, Linear Programming and Rounding-General algorithm
Lecture: general algorithm
()
Slides
Bin Packing, Linear Programming and Rounding-Bin packing: conclusion
Lecture: conclusion
()
Slides
Bin Packing, Linear Programming and Rounding-Exercises
Practice Exercises
All slides together in one file
Set Cover and Randomized Rounding-Set Cover Definition
Lecture: definition
()
Slides
Set Cover and Randomized Rounding-Randomized Rounding
Lecture: randomized rounding
()
Slides
Set Cover and Randomized Rounding-Cost Analysis
Lecture: cost analysis
()
Slides
Set Cover and Randomized Rounding-Coverage Analysis
Lecture: coverage analysis
()
Slides
Set Cover and Randomized Rounding-Iterated Algorithm
Lecture: iterated algorithm
()
Slides
Set Cover and Randomized Rounding-Stopping Time Algorithm
Lecture: stopping time algorithm
()
Slides
Set Cover and Randomized Rounding-Stopping Time Analysis
Lecture: stopping time analysis
()
Slides
Set Cover and Randomized Rounding-Remarks
Lecture:final remarks
()
Slides
A reference on this stopping time analysis
Set Cover and Randomized Rounding-Exerices
Practise Exercise
All slides together in one file
Multiway Cut and Randomized Rounding-What is the Multiway Cut problem?
Lecture: definition
()
Slides
Multiway Cut and Randomized Rounding-A linear programming relaxation
Lecture: linear programming relaxation
()
Slides
Multiway Cut and Randomized Rounding-Randomized rounding
Lecture: randomized rounding
()
Slides
Multiway Cut and Randomized Rounding-Analysis
Lecture: analysis
()
Slides
Multiway Cut and Randomized Rounding-Conclusion
Lecture: conclusion
()
Slides
Multiway Cut and Randomized Rounding-Exercises
Practice exercise
All Chapter Slides together in one file
Slides for all chapters of Approx Algs Part 1 together in one file