Supermodularity in mean-partition problems

Abstract

Supermodularity of the lambda function which defines a permutation polytope has proved to be crucial for the polytope to have some nice fundamental properties. Supermodularity has been established for the lambda function for the sum-partition problem under various models. On the other hand, supermodularity has not been established for the mean-partition problem even for the most basic labeled single-shape model. In this paper, we fill this gap and also settle for all other models except one. We further extend our results to other types of supermodularity.