On Equivalence of M${}^{♮}$-concavity of a Set Function and Submodularity of Its Conjugate

Abstract

A fundamental theorem in discrete convex analysis states that a set function is M${}^{♮}$-concave if and only if its conjugate function is submodular. This paper gives a new proof to this fact.

10 pages