Multimodularity, Convexity and Optimization Properties.

摘要

The authors investigate in this paper the properties of multimodular functions. In doing so the authors give alternative proofs for properties already established by Hajek, and they extend his results. In particular, the authors show the relation between convexity and multimodularity, which allows them to restrict the study of multimodular functions to convex subsets of Z(sup m). The authors then obtain general optimization results for average costs related to a sequence of multimodular functions. In particular, the authors establish lower bounds, and show that the expected average problem is optimized by using balanced sequences. The authors finally illustrate the usefulness of this theory in admission control into a D/D/1 queue with fixed batch arrivals, with no state information. The authors show that the balanced policy minimizes the average queue length for the case of an infinite queue, but not for the case of a finite queue. When further adding a constraint on the losses, it is shown that a balanced policy is also optimal for the finite queue case.