Odd submodular functions, Dilworth functions and discrete convex functions

Odd submodular functions, Dilworth functions and discrete convex functions

0.00 Avg rating0 Votes
Article ID: iaor1988185
Country: United States
Volume: 13
Issue: 3
Start Page Number: 435
End Page Number: 446
Publication Date: Aug 1988
Journal: Mathematics of Operations Research
Authors:
Abstract:

Three set-function classes more general than submodular ones are discussed. An odd submodular function defines a box totally dual integral system. An integral odd submodular function and its Dilworth truncation, i.e., a Dilworth function, give rise to the same polyhedron with integral vertices. The minimum of two submodular functions is an odd submodular function. The convolution of two submodular functions is a Dilworth function. A Dilworth function is a discrete convex function. A discrete convex function can be characterized by its convex hull, subgradients, epigraph and general subadditivity. Discrete convexity is preserved under many natural operations.

Reviews

Required fields are marked *. Your email address will not be published.