Extensions of functions of 0-1 variables and applications to combinatorial optimization
Ivan Singer · Numerical Functional Analysis and Optimization · 1985
For in § 2 we introduce and study “tight extensions” fD : [0, 1]n → R, defined on each n-simplex Di of a triangulation D of [0,1]n, with all vertices in {0,1}n, as the unique affine function which interpolates f at the vertices of Di. In § 3 we study convexity of tight extensions. In §4 we show the existence of polyhedral convex (generally, non-tight) extensions. As applications, in §5 we give some duality theorems for minimization and maximization of submodular functions and in §6 (Appendix) we obtain new insight into the “greedy solutions” of a certain linear maximization problem.