Better Know A Theorem: Sandwich Theorems
Rather than a complete explanation, today is an excerpt from “Combinatorial Optimization” by Lex Schrijver; if for no other reason, because of the name (tied for best with the “hairy ball theorem”).
A. Frank in 1982 showed the following ‘discrete sandwich theorem’ (analogous to the ‘continuous sandwich theorem’, stating the existence of a linear function between a convex and a concave function):
Corollary 46.2b (Frank’s discrete sandwich theorem). Let f be a submodular and g be a supermodular set function on S, with g ≤ f. Then there exists a modular set function h with g ≤ h ≤ f. If f and g are integer, h can be taken integer.
Filed under: b.k.a.t., combinatorial optimization, food | Leave a Comment