head-to-head problem
-
The objective function of the main dual problem is the difference between the objective functions of the main problem and the dual problem, which is zero in the optimal solution. Also, the constraint condition is the combined constraint condition of the main problem and the dual problem.
Primal-dual http://www.cs.toronto.edu/~slwang/primal-dual.pdf
https://img.atcoder.jp/agc043/editorial.pdf
http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H22-slide-iwata.pdf
http://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2008/note/14.pdf
Minimal Cost Flow (Primal-Dual) | Luzhiled’s memo
This page is auto-translated from /nishio/主双対アルゴリズム using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.