Model-driven optimization using adaptive probes

Conference Paper

In several applications such as databases, planning, and sensor networks, parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system (as captured by some objective function over the parameters) is significantly improved if some of these parameters can be probed or observed. In a resource constrained situation, deciding which parameters to observe in order to optimize system performance itself becomes an interesting and important optimization problem. This problem is the focus of this paper. Unfortunately designing optimal observation schemes is NPHard even for the simplest objective functions, leading to the study of approximation algorithms. In this paper we present general techniques for designing non-adaptive probing algorithms which are at most a constant factor worse than optimal adaptive probing schemes. Interestingly, this shows that for several problems of interest, while probing yields significant improvement in the objective function, being adaptive about the probing is not beneficial beyond constant factors.

Duke Authors

Cited Authors

  • Guha, S; Munagala, K

Published Date

  • January 1, 2007

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Volume / Issue

  • 07-09-January-2007 /

Start / End Page

  • 308 - 317

International Standard Book Number 13 (ISBN-13)

  • 9780898716245

Citation Source

  • Scopus