Multimodularity, Convexity, and Optimization Properties

In this paper we investigate the properties of multimodular functions. In doing so we give elementary proofs for properties already established by Hajek and we generalize some of his results. In particular, we extend the relation between convexity and multimodularity to some convex subsets of z m ....

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2000-05, Vol.25 (2), p.324-347
Main Authors: Altman, Eitan, Gaujal, Bruno, Hordijk, Arie
Format: Article
Language:English
Subjects:
admission control into a queue
Atoms
Average cost
Computer Science
Convex domains
Convexity
Coordinate systems
Cost functions
Functional equations
Functions
Integers
Linear interpolation
Mathematical functions
Mathematical optimization
Mathematics
Multimodular functions
Networking and Internet Architecture
Operations research
Optimization and Control
Probability
Queuing
regular sequences
Studies
Urelements
Workloads
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we investigate the properties of multimodular functions. In doing so we give elementary proofs for properties already established by Hajek and we generalize some of his results. In particular, we extend the relation 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 optimized by using regular 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 regular 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 regular policy is also optimal for the finite queue case.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.25.2.324.12230