Linear Programming Duality-Duality by example
Linear programming duality - example
()
Slides
Comment
Linear Programming Duality-Properties of LP duality
Properties of LP duality
()
Slides
Linear Programming Duality-Geometry of LP duality
Geometry of LP duality
()
Slides
Linear Programming Duality-Proof of weak duality
Slides
Proof of weak duality theorem
()
Linear Programming Duality-Changing the form of the LP
Slides
Changing the form of the LP
()
Linear Programming Duality-Complementary slackness
Slides
Complementary slackness
()
Linear Programming Duality-Primal-dual algorithms
Primal-dual algorithms
()
Slides
Linear Programming Duality-Vertex Cover by primal-dual
Slides
Vertex cover by primal-dual
()
Linear Programming Duality-Conclusion
Slides
Conclusion
()
Linear Programming Duality-Exercises
Slides-all
Steiner Forest and Primal-Dual Approximation Algorithms-Problem definition
Slides
Problem definition
()
Steiner Forest and Primal-Dual Approximation Algorithms-A special case: Steiner tree
Slides
A special case: Steiner tree
()
Steiner Forest and Primal-Dual Approximation Algorithms-A LP relaxation for Steiner forest...
Slides
LP relaxation for Steiner forest
()
Steiner Forest and Primal-Dual Approximation Algorithms-...and its dual
Slides
... and its dual
()
Steiner Forest and Primal-Dual Approximation Algorithms-Primal-dual algorithm, Part 1
Slides
Primal-dual algorithm, Part1
()
Steiner Forest and Primal-Dual Approximation Algorithms-Primal-dual algorithm, Part 2
Slides
Primal-dual algorithm,Part 2
()
Steiner Forest and Primal-Dual Approximation Algorithms-Analysis
Slides
Analysis
()
Steiner Forest and Primal-Dual Approximation Algorithms-Proof of the main lemma
Slides
Proof of the main lemma
()
Steiner Forest and Primal-Dual Approximation Algorithms-Exercises
Slides-all
Facility Location and Primal-Dual Approximation Algorithms-Problem definition
Slides
Problem definition
()
Facility Location and Primal-Dual Approximation Algorithms-A linear programming relaxation...
Slides
A linear programming relaxation
()
Facility Location and Primal-Dual Approximation Algorithms-... and its dual
Slides
...and its dual
()
Facility Location and Primal-Dual Approximation Algorithms-A primal-dual algorithm
Slides
A primal-dual algorithm
()
Facility Location and Primal-Dual Approximation Algorithms-Analyzing the service cost
Slides
Analyzing the service cost
()
Facility Location and Primal-Dual Approximation Algorithms-Analyzing the facility opening cost
Slides
Analyzing the facility opening cost
()
Facility Location and Primal-Dual Approximation Algorithms-A better primal-dual algorithm
Slides
A better algorithm
()
Facility Location and Primal-Dual Approximation Algorithms-Analysis
Slides
Analysis
()
Facility Location and Primal-Dual Approximation Algorithms-Conclusion
Slides
Conclusion
()
Facility Location and Primal-Dual Approximation Algorithms-Exercises
Slides-all
Maximum Cut and Semi-Definite Programming-Definition
Definition
()
Slides
Maximum Cut and Semi-Definite Programming-A 2-approximation
A 2-approximation
()
Slides
Maximum Cut and Semi-Definite Programming-A linear programming relaxation...
A linear programming relaxation...
()
Slides
Maximum Cut and Semi-Definite Programming-... that has an integrality gap of almost 2 (overview)
Slides
...with an integrality gap of almost 2
()
Maximum Cut and Semi-Definite Programming-Proof of lemma
Slides
Proof of Lemma
()
Maximum Cut and Semi-Definite Programming-A quadratic programming relaxation
A quadratic programming relaxation
()
Slides
Maximum Cut and Semi-Definite Programming-General facts about semidefinite programming
Slides
General facts about semidefinite programming
()
Maximum Cut and Semi-Definite Programming-A rounding algorithm
Slides
A rounding algorithm
()
Maximum Cut and Semi-Definite Programming-Analysis
Sldies
Analysis
()
Maximum Cut and Semi-Definite Programming-General facts about Maxcut
General facts about MaxCut
()
Slides
Maximum Cut and Semi-Definite Programming-Exercises
Slides-all
The end!
()
Comment