Multimodularity, Convexity and Optimization Properties

Eitan Altman 1 Bruno Gaujal 2 Arie Hordijk
2 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We investigate in this paper the properties of multimodular functions. In doing so we give alternative proofs for properties already established by Hajek, and we extend his results. In particular, we show the relation between convexity and multimodularity, which allows us to restrict the study of multimodular functions to convex subsets of $\Z^m$. We then obtain general optimization results for average costs related to a sequence of multimodular functions. In particular, we establish lower bounds, and show that the expected average problem is optimized by using balanced sequences. We finally illustrate the usefulness of this theory in admission control into a D/D/1 queue with fixed batch arrivals, with no state information. We 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 case of finite queue.
Type de document :
RR-3181, INRIA. 1997
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:05:23
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:48:35



  • HAL Id : inria-00073508, version 1



Eitan Altman, Bruno Gaujal, Arie Hordijk. Multimodularity, Convexity and Optimization Properties. RR-3181, INRIA. 1997. 〈inria-00073508〉



Consultations de la notice


Téléchargements de fichiers