 Mar 2023

www.dl.behinehyab.com www.dl.behinehyab.com

7.4 SHORTEST AUGMENTING PATH ALGORITHM
Not quite Dinic, Not quite Edmonds Karp. It's something in between.

 Feb 2023

www.dl.behinehyab.com www.dl.behinehyab.com

Property 2.4.
The \(z(0)\) is the objective function whenever the potential for all the vertices are zero, hence it's the objective of the original problem. In this claim we prove that the difference between the problem with zero porential and the problem with some potential and a "reduced costs" is a constant away, and hence, solving the problem with the reduced costs is the same as solving the original.
Is this some type of primal dual algoithm that we are dong here...

.IS FLOW DECOMPOSITION ALGORITHMS
Read this to compelemnt the lectures.

Property 2.5
Properties of Reduced costs network. A reduced cost label is created via a potential label on the vertices of the graph. 1. The reduced costs on a path equals to the costs itself. 2. The sum of reduced costs along any path is the original cost minus the differences between the destination and the source.
It's like a line integer over a conservative field in physics you know, the value we get by subtracting the reduced costs over circle and path gives the differences in the potential. Just like a conservative field in physics.

Working with Residual Networks
Residual Network is a transform on the network given an existing feasible flow.
