Computer Science – Data Structures and Algorithms
Scientific paper
2008-12-04
Computer Science
Data Structures and Algorithms
Journal version of the paper "Model-driven Optimization using Adaptive Probes" that appeared in the ACM-SIAM Symposium on Disc
Scientific 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 general problem is the focus of this paper. One of the most important considerations in this framework is whether adaptivity is required for the observations. Adaptive observations introduce blocking or sequential operations in the system whereas non-adaptive observations can be performed in parallel. One of the important questions in this regard is to characterize the benefit of adaptivity for probes and observation. We present general techniques for designing constant factor approximations to the optimal observation schemes for several widely used scheduling and metric objective functions. We show a unifying technique that relates this optimization problem to the outlier version of the corresponding deterministic optimization. By making this connection, our technique shows constant factor upper bounds for the benefit of adaptivity of the observation schemes. We show that while probing yields significant improvement in the objective function, being adaptive about the probing is not beneficial beyond constant factors.
Guha Sudipto
Munagala Kamesh
No associations
LandOfFree
Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-136508