This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Foldes, S. Articles by Hammer, P. L. Search for Related Content

Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions

Institute of Mathematics, Tampere University of Technology, PL 553, 33101 Tampere, Finland
RUTCOR–Rutgers Center for Operations Research, Rutgers University, 640 Bartholomew Road, Piscataway, New Jersey 08854-8003
stephan.foldes{at}tut.fi
hammer{at}rutcor.rutgers.edu

Classes of set functions defined by the positivity or negativity of the higher-order derivatives of their pseudo-Boolean polynomial representations generalize those of monotone, supermodular, and submodular functions. In this paper, these classes are characterized by functional inequalities and are shown to be closed both under algebraic closure conditions and a local closure criterion. It is shown that for every m 1, in addition to the class of all set functions, there are only three other classes satisfying these algebraic and local closure conditions: those having positive, respectively negative, mth-order derivatives, and those having a polynomial representation of degree less than m.

Key Words: set functions; Boolean functions; pseudo-Boolean functions; submodularity; supermodularity; discrete derivatives; Post classes; functional inequalities; functional equations; minors; local closure
History: Received: October 30, 2002; revision received: February 27, 2004;