A Min-Max Theorem for Transversal Submodular Functions and Its Implications

Abstract

Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462] introduced a concept of $k$-submodular function as a generalization of ordinary submodular (set) functions and bisubmodular functions and obtained a min-max theorem for the minimization of $k$-submodular functions. Also Kuivinen [Discrete Optim., 8 (2011), pp. 459--477] considered submodular functions on (product lattices of) diamonds and showed a min-max theorem for the minimization of submodular functions on diamonds. In the present paper we consider a common generalization of $k$-submodular functions and submodular functions on diamonds, which we call a transversal submodular function (a t-submodular function, for short). We show a min-max theorem for the minimization of t-submodular functions in terms of a new norm composed of $\ell_1$ and $\ell_\infty$ norms. This reveals a relationship between the obtained min-max theorem and that for the minimization of ordinary submodular set functions due to Edmonds [Submodular functions, matroids, and certain polyhedra, in Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, New York, 1970, pp. 69--87].We also show how our min-max theorem for t-submodular functions can be used to prove the min-max theorem for $k$-submodular functions by Huber and Kolmogorov and that for submodular functions on diamonds by Kuivinen. Moreover, we show a counterexample to a characterization, given by Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462], of extreme points of the $k$-submodular polyhedron and make it a correct one by fixing a flaw therein.