### Better Know A Theorem: Sandwich Theorems

13Jul07

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). Letfbe a submodular andgbe a supermodular set function onS, withg≤f. Then there exists a modular set functionhwithg≤h≤f. Iffandgare integer,hcan be taken integer.

Advertisements

Filed under: b.k.a.t., combinatorial optimization, food | Leave a Comment

## No Responses Yet to “Better Know A Theorem: Sandwich Theorems”