Linear Programming-Course Introduction
Earn Academic Credit for your Work!
Course Support
Linear Programming-What is a Linear Program?
Introduction to Linear Programming
()
What is a Linear Program?
()
Example: Cake-Sharing Problem
()
Solving Linear Programs
()
Linear Programming-Network Flow Problems and Linear Programming
Network Flow Problems and Linear Programs
()
Linear Programming-Geometry of Linear Programs
Geometry of Linear Programs
()
Linear Programming-Algorithms for Linear Programs: A brief overview
Algorithms for Solving Linear Programs
()
Integer Linear Programming-What is an Integer Linear Program?
What is an Integer Linear Program?
()
Formal Introduction to Integer Linear Programs
()
Integer Linear Programming-NP-Hardness of Integer Linear Programs
NP Hardness of Integer Linear Programming
()
Integer Linear Programming-Vertex Cover as Integer Linear Program
Vertex Cover as an Integer Linear Program
()
Integer Linear Programming-Linear Programming Approximations of Vertex Cover
Linear Programming Approximations to Vertex Cover
()
Integer Linear Programming-Solving Integer Linear Programs using Branch and Bound Algorithm
Branch and Bound Algorithm for Solving Integer Linear Programs
()
Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT-Approximation Algorithms and Approximation Ratios: Introduction
Introduction to Approximation Algorithms
()
Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT-Jobshop Minimum Makespan Scheduling
Introduction to Jobshop Scheduling and Algorithm Design
()
Analysis of Jobshop Scheduling
()
Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT-Vertex Cover
Approximation Algorithms for Vertex Cover and their Analysis
()
Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT-Maximum Satisfiability Problem
Approximation Algorithms for the Maximum Satisfiability Problem
()
Travelling Salesperson Problem (TSP) and Approximation Schemes-Travelling Salesperson Problem (TSP)
Introduction to TSP and its applications
()
NP-Hardness of TSPs
()
Hardness of Approximating General TSPs
()
Travelling Salesperson Problem (TSP) and Approximation Schemes-Exact Algorithms for TSP
Held and Karp's Dynamic Programming Algorithm
()
Integer Linear Programming Formulation
()
Subtours and Subtour Elimination Formulation
()
Travelling Salesperson Problem (TSP) and Approximation Schemes-Approximation Algorithm for TSP
Metric TSP and Shortcutting
()
Eulerian Walks for approximating TSPs
()
Christofides Algorithm and its Analysis
()
Travelling Salesperson Problem (TSP) and Approximation Schemes-Heuristics: A Brief Tour
Heuristics for TSPs
()
Travelling Salesperson Problem (TSP) and Approximation Schemes-Approximation Schemes and the Knapsack Problem
Full Polynomial Time Approximation Scheme and Knapsack
()