Multimodularity, convexity, and optimization properties

In this paper we investigate the properties of multimodular functions. In d oing so we give elementary proofs for properties already established by Haj ek and we generalize some of his results. In particular, we extend the rela tion between convexity and multimodularity to some convex subsets of Z(m). We also obtain general optimization results for average costs related to a sequence of multimodular functions rather than to a single function. Under this general context, we show that the expected average cost problem is opt imized by using regular sequences. We finally illustrate the usefulness of this theory in admission control into a D/D/1 queue with fixed batch arriva ls, with no state information. We show that the regular policy minimizes th e average queue length for the case of an infinite queue, but not for the c ase of a finite queue. When further adding a constraint on the losses, it i s shown that a regular policy is also optimal for the finite queue case.