Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship between some great algorithms (like disjktra's shortest path algorithm, edmonds' maximum matching algorithm ...) and LP duality. My question is about a general framework on constructing combinatorial algorithms based on LP duality. For a given problem what are the necessary and sufficient conditions for the existence of such algorithms. I think duality gap should be the first necessary condition and to have a totally unimodal matrix could be sufficient.Maybe the answer is written in that book and I should read it again carefully.
Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.
ds.algorithms;primal dual