linear algorithm Simplex method

2020-09-17

ILP

ILP is NP-hard, therefore we can reduce any NP-complete optimization problem to ILP.

the optimal solution of the LP is only better than the optimal of ILP:every feasible point from the ILP is still feasible in the LP

LP

linear programs are solvable in polynomial time
image

standard form

image

Maximum Flow

image

Vertex Cover

image

ILP for vertex cover

image

LP relaxation

image

Simplex method

转轴操作

理解为从一个顶点走向另一个顶点

knapsack problem

image

LP duality

The dual of the dual of a linear program is the linear program itself

Weak Duality

image

Strong Duality

image

https://tcs.nju.edu.cn/wiki/index.php?title=%E9%AB%98%E7%BA%A7%E7%AE%97%E6%B3%95_(Fall_2022)
http://tcs.nju.edu.cn/slides/aa2022/DP.pdf