Linear Programming

LP solution space

Slov methodes

• Simplex method LP slover

• Ellipsoid method LP slover

• Interior point methods
  LP Optimization = Separation

Integer Linear Programs
LP Duality

Maximum Matching as LP
Minmal Vertex Cover as LP
Minimum-Cost Flow as LP
The Knapsack Problem as LP
Weighted Vertex Cover as LP

Simple Example