Applications of Linear Programming Duality in Combinatorics – Practical Uses

Question

So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's theorem and Menger's theorem. It's neat that these theorems, all equivalent to one another, can be seen to follow from a single framework.

I was wondering if there are other such interesting applications of LP duality (or more general kinds of duality) in combinatorics, perhaps of a different flavor? Is there a good reference for these topics? The more surprising the applications, the better.

Answer 1

How about Boosting¹ and the Hardcore Lemma, as described in this paper?

Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)

The Hardcore Lemma can be proved via LP duality:

"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."

Their proof of their main result "uses duality of linear programming (or, equivalently, the finite dimensional Hahn-Banach Theorem) in the form of the min-max theorem for two-player zero-sum games."

Another summary of Impagliazzo's Hardcore Lemma:

"Every hard function has a hardcore subset such that the restricted function becomes extremely hard to compute."

---

¹ Boosting constitutes "a family of machine learning algorithms which convert weak learners to strong ones." ... "[M]ost boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."