# Multimodularity, Convexity and Optimization Properties

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.
Mots-clés :
Type de document :
Rapport
RR-3181, INRIA. 1997
Domaine :

Littérature citée [1 références]

https://hal.inria.fr/inria-00073508
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:05:23
Dernière modification le : jeudi 11 janvier 2018 - 16:03:00
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:48:35

### Identifiants

• HAL Id : inria-00073508, version 1

### Citation

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

### Métriques

Consultations de la notice

## 252

Téléchargements de fichiers