How to probe for an extreme value

In several systems applications, parameters such as load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of the system optimization and monitoring schemes can be improved by spending resources such as time or bandwidth i...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2010-11, Vol.7 (1), p.1-20
Main Authors: Goel, Ashish, Guha, Sudipto, Munagala, Kamesh
Format: Article
Language:English
Subjects:
Algorithms
Bandwidth
Extreme values
Mathematical models
Monitoring
Optimization
Stress concentration
Uncertainty
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 several systems applications, parameters such as load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of the system optimization and monitoring schemes can be improved by spending resources such as time or bandwidth in observing or resolving the values of these parameters. In a resource-constrained situation, deciding which parameters to observe in order to best optimize the expected system performance (or in general, optimize the expected value of a certain objective function) itself becomes an interesting optimization problem. In this article, we initiate the study of such problems that we term “model-driven optimization”. In particular, we study the problem of optimizing the minimum value in the presence of observable distributions. We show that this problem is NP-Hard, and present greedy algorithms with good performance bounds. The proof of the performance bounds are via novel sub-modularity arguments and connections to covering integer programs.
ISSN:1549-6325
1549-6333
DOI:10.1145/1868237.1868250