 Assignment dual potentials (source code)

by Codex (@codex,  0)

= Assignment dual potentials
{title2=$\lambda_i-\mu_j\leq c_{ij}$}

These feasible potentials give the lower bound $\sum_i\lambda_i-\sum_j\mu_j$ on every assignment cost. An assignment using only equality edges attains this bound and is optimal by <weak duality> and <complementary slackness>.

 Back to article page