Contents
Overview of Course
Splay Trees
Amortized Time for Splay Trees
Maintaining Disjoint Sets
Binomial heaps
F-heap
Minimum Spanning Trees
Fredman-Tarjan MST Algorithm
Branching Problem
Light Approximate Shortest Path Trees
Matchings
Hopcroft-Karp Matching Algorithm
Two Processor Scheduling
Assignment Problem
Network Flow - Maximum Flow Problem
The Max Flow Problem
An O(n) Max-Flow Algorithm
Vertex Covers and Network Flow
Planar Graphs
Planar Graphs
Graph Coloring
Graph Minor Theorem and other CS Collectibles
The Min Cost Flow Problem
Min Mean Cycle Problem
Shortest Path based Algorithm for Min Cost Flows
NP-completeness
NP-Completeness
NP-Completeness
More on NP-Completeness
Satisfiability
Linear Programming
Bin Packing
Nemhauser-Trotter Theorem
Vertex Cover
Weighted Vertex Cover
A ( − f(n)) Approximation Algorithm for the Vertex Cover Problem
Approximation Algorithms: Set Cover
Approximation Algorithms: Set Cover and Max Coverage
Approximation Algorithms: K-Centers
Multi-cost Minimum Spanning Trees
Set and Vertex Cover Approximations: Randomized Algorithms
Steiner Tree Problem
Traveling Salesperson and Chinese Postman Problem
Vehicle Routing Problems:Stacker Crane
Vehicle Routing Problems: Capacity Bounded Vehicles
Unit Capacity Problem (-delivery TSP)
K-capacity problem
Unbounded capacity problem
Lower Bounds on Approximations
Lower Bounds on Approximations (contd)
Linear Programming: The Use of Duality
Using duality to analyze (and design) approximation algorithms
A General Approximation Technique for Constrained Forest Problems
The Primal-Dual Method for Linear Programming
The Primal-Dual Method applied to Max weight perfect matching in bipartite graphs
On Line vs. Off Line: A Measure for Quality Evaluation