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

Kazuo Murota, Akiyoshi Shioura

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 pro…