What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

50 Views Asked by At

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. However, it is usually remarked that they take to account only a 'particular type' of dual variables, for example in the Blossom Algorithm (http://theory.stanford.edu/~jvondrak/CS369P-files/lec6.pdf), the dual variables 'uses only sets from some laminar family $\Omega$'.

Now my query is essentially equivalent to - why this family, moreover , why only this family. What suffices their use and what motivates their construction? Also as a follow up - Does it relate to total dual integrality and (if yes, then) how?